#ifdef DEBUG #define _GLIBCXX_DEBUG #define UNTIE ios_base::sync_with_stdio( false ); cin.tie( nullptr ); signal( SIGABRT , &AlertAbort ) #define DEXPR( LL , BOUND , VALUE , DEBUG_VALUE ) CEXPR( LL , BOUND , DEBUG_VALUE ) #define CERR( MESSAGE ) cerr << MESSAGE << endl; #define COUT( ANSWER ) cout << ANSWER << endl #define ASSERT( A , MIN , MAX ) CERR( "ASSERTチェック: " << ( MIN ) << ( ( MIN ) <= A ? "<=" : ">" ) << A << ( A <= ( MAX ) ? "<=" : ">" ) << ( MAX ) ); assert( ( MIN ) <= A && A <= ( MAX ) ) #else #pragma GCC optimize ( "O3" ) #pragma GCC optimize( "unroll-loops" ) #pragma GCC target ( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" ) #define UNTIE ios_base::sync_with_stdio( false ); cin.tie( nullptr ) #define DEXPR( LL , BOUND , VALUE , DEBUG_VALUE ) CEXPR( LL , BOUND , VALUE ) #define CERR( MESSAGE ) #define COUT( ANSWER ) cout << ANSWER << "\n" #define ASSERT( A , MIN , MAX ) assert( ( MIN ) <= A && A <= ( MAX ) ) #endif #include using namespace std; #define MAIN main #define TYPE_OF( VAR ) decay_t #define CEXPR( LL , BOUND , VALUE ) constexpr LL BOUND = VALUE #define CIN( LL , A ) LL A; cin >> A #define CIN_ASSERT( A , MIN , MAX ) TYPE_OF( MAX ) A; SET_ASSERT( A , MIN , MAX ) #define FOR( VAR , INITIAL , FINAL_PLUS_ONE ) for( TYPE_OF( FINAL_PLUS_ONE ) VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ ) #define QUIT return 0 #define SET_ASSERT( A , MIN , MAX ) cin >> A; ASSERT( A , MIN , MAX ) #define RETURN( ANSWER ) COUT( ( ANSWER ) ); QUIT #ifdef DEBUG inline void AlertAbort( int n ) { CERR( "abort関数が呼ばれました。assertマクロのメッセージが出力されていない場合はオーバーフローの有無を確認をしてください。" ); } #endif // 圧縮用 #define TE template #define TY typename #define US using #define ST static #define IN inline #define CL class #define PU public #define OP operator #define CE constexpr #define CO const #define NE noexcept #define RE return #define WH while #define VO void #define VE vector #define LI list #define BE begin #define EN end #define SZ size #define MO move #define TH this #define CRI CO int& #define CRUI CO uint& #define CRL CO ll& TE CL UnionFindForest{PU:uint m_node_SZ;uint m_root_SZ;VE m_pred;VE m_height;VE m_w;IN UnionFindForest(CRUI SZ);CRUI RootOfNode(CRUI num);TE TY V> VO SetRoot(V& a)CO;IN T Weight(CRUI num0,CRUI num1);IN CRUI SZOfNode()CO NE;IN CRUI SZOfRoot()CO NE;bool Graft(CRUI num0,CRUI num1,CO T& w = 0);}; TE IN UnionFindForest::UnionFindForest(CRUI SZ):m_node_SZ(SZ),m_root_SZ(m_node_SZ),m_pred(m_node_SZ),m_height(m_node_SZ,1),m_w(m_node_SZ){for(uint i = 0;i < m_node_SZ;i++){m_pred[i]= i;}}TE CRUI UnionFindForest::RootOfNode(CRUI num){uint& pred1 = m_pred[num];WH(true){uint& pred2 = m_pred[pred1];if(pred1 == pred2){break;}m_w[num]+= m_w[pred1]+= m_w[pred2];pred1 = pred2 = m_pred[pred2];}RE pred1;}TE TE TY V>VO UnionFindForest::SetRoot(V& a)CO{a.clear();for(uint i = 0;i < m_node_SZ;i++){if(i == m_pred[i]){a.push_back(i);}}RE;}TE T UnionFindForest::Weight(CRUI num0,CRUI num1){assert(num0 < m_node_SZ && num1 < m_node_SZ);CRUI root0 = RootOfNode(num0);CRUI root1 = RootOfNode(num1);assert(root0 == root1);RE m_w[num1]- m_w[num0];}TE IN CRUI UnionFindForest::SZOfNode()CO NE{RE m_node_SZ;}TE IN CRUI UnionFindForest::SZOfRoot()CO NE{RE m_root_SZ;}TE bool UnionFindForest::Graft(CRUI num0,CRUI num1,CO T& w){assert(num0 < m_node_SZ && num1 < m_node_SZ);CRUI root0 = RootOfNode(num0);CRUI root1 = RootOfNode(num1);if(root0 == root1){RE Weight(num0,num1)== w;}uint& height0 = m_height[root0];CRUI height1 = m_height[root1];CO uint* p_reMOd_root;CO uint* p_reMOd_node;CO uint* p_kept_root;if(height0 < height1){p_reMOd_root = &root0;p_reMOd_node = &num0;p_kept_root = &root1;m_w[*p_reMOd_root]-= w - m_w[num1]+ m_w[num0];}else{if(height0 == height1){height0++;}p_reMOd_root = &root1;p_reMOd_node = &num1;p_kept_root = &root0;m_w[*p_reMOd_root]+= w - m_w[num1]+ m_w[num0];}if(*p_reMOd_node != *p_reMOd_root){m_w[*p_reMOd_node]+= m_w[*p_reMOd_root];}m_pred[*p_reMOd_node]= m_pred[*p_reMOd_root]= *p_kept_root;m_root_SZ--;RE true;} inline DEXPR( int , bound_N , 100000 , 100 ); // 0が5個 TYPE_OF( bound_N ) N; inline DEXPR( int , bound_M , 100000 , 100 ); // 0が5個 TYPE_OF( bound_M ) M; int MAIN() { UNTIE; SET_ASSERT( N , 2 , bound_N ); SET_ASSERT( M , 1 , bound_M ); assert( M / ( N - 1 ) <= N ); UnionFindForest<> uff{ N * 2 }; string equiv[2] = { "<==>" , "<=/=>" }; FOR( m , 0 , M ){ CIN_ASSERT( i , 1 , N ); CIN( string , E ); CIN_ASSERT( j , i + 1 , N ); i--; j--; int b = E == equiv[0] ? 0 : ( assert( E == equiv[1] ) , 1 ); uff.Graft( i , j + b * N ); uff.Graft( i + N , j + ( 1 - b ) * N ); } int count_chosen = 0; int chosen_connected_component_num[bound_N*2] = {}; FOR( i , 0 , N ){ const int& connected_component_num_i = uff.RootOfNode( i ); const int& connected_component_num_i_N = uff.RootOfNode( i + N ); if( connected_component_num_i == connected_component_num_i_N ){ RETURN( "No" ); } int& chosen_connected_component_num_i = chosen_connected_component_num[connected_component_num_i]; if( chosen_connected_component_num_i == 0 ){ chosen_connected_component_num_i = 1; chosen_connected_component_num[connected_component_num_i_N] = 2; } if( chosen_connected_component_num_i == 1 ){ count_chosen++; } } bool non_flip; if( count_chosen * 2 >= N ){ non_flip = true; } else { non_flip = false; count_chosen = N - count_chosen; } COUT( "Yes" ); COUT( count_chosen ); FOR( i , 0 , N ){ const int& connected_component_num_i = uff.RootOfNode( i ); if( ( chosen_connected_component_num[connected_component_num_i] == 1 ) == non_flip ){ cout << i + 1 << " \n"[--count_chosen==0]; } } QUIT; }