#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 // Resetはm_foundとm_prevを初期化 // Shiftはm_foundとm_prevを非初期化 // Breadth/DepthFirstConnectedComponentSearchは無向グラフの連結成分を色分け&数え上げ // Next()の反復でm_initから到達可能な頂点を全探索。 // 計算量O((m_initの連結成分)+(m_initの連結成分におけるEのサイズの合計)) #define DECLARATION_OF_FIRST_SEARCH( BREADTH ) \ template \ class BREADTH ## FirstSearch_Body \ { \ \ protected: \ int m_V; \ int m_init; \ list m_next; \ bool m_found[V_max]; \ int m_prev[V_max]; \ \ public: \ inline BREADTH ## FirstSearch_Body( const int& V ); \ inline BREADTH ## FirstSearch_Body( const int& V , const int& init ); \ \ inline void Reset( const int& init ); \ inline void Shift( const int& init ); \ \ inline const int& size() const; \ inline const int& init() const; \ inline bool& found( const int& i ); \ inline const int& prev( const int& i ) const; \ \ int Next(); \ \ private: \ virtual list e( const int& t ) = 0; \ \ }; \ \ template E(const int&)> \ class BREADTH ## FirstSearch : \ public BREADTH ## FirstSearch_Body \ { \ \ public: \ \ template inline BREADTH ## FirstSearch( const Args&... args ); \ \ private: \ inline list e( const int& t ); \ \ }; \ \ template E(const int&)> void BREADTH ## FirstConnectedComponentSearch( const int& V , int ( &cc_numx )[V_max] , int& count ); \ #define DEFINITION_OF_FIRST_SEARCH( BREADTH , PUSH ) \ template inline BREADTH ## FirstSearch_Body::BREADTH ## FirstSearch_Body( const int& V ) : m_V( V ) , m_init() , m_next() , m_found() , m_prev() { assert( m_V <= V_max ); for( int i = 0 ; i < m_V ; i++ ){ m_prev[i] = -1; } } \ template inline BREADTH ## FirstSearch_Body::BREADTH ## FirstSearch_Body( const int& V , const int& init ) : BREADTH ## FirstSearch_Body( V ) { m_init = init; m_next.push_back( m_init ); m_found[m_init] = true; } \ template E(const int&)> template inline BREADTH ## FirstSearch::BREADTH ## FirstSearch( const Args&... args ) : BREADTH ## FirstSearch_Body( args... ) {} \ \ template inline void BREADTH ## FirstSearch_Body::Reset( const int& init ) { m_init = init; assert( m_init < m_V ); m_next.clear(); m_next.push_back( m_init ); for( int i = 0 ; i < m_V ; i++ ){ m_found[i] = i == m_init; m_prev[i] = -1; } } \ template inline void BREADTH ## FirstSearch_Body::Shift( const int& init ) { m_init = init; assert( m_init < m_V ); m_next.clear(); if( ! m_found[m_init] ){ m_next.push_back( m_init ); m_found[m_init] = true; } } \ \ template inline const int& BREADTH ## FirstSearch_Body::size() const { return m_V; } \ template inline const int& BREADTH ## FirstSearch_Body::init() const { return m_init; } \ template inline bool& BREADTH ## FirstSearch_Body::found( const int& i ) { assert( i < m_V ); return m_found[i]; } \ template inline const int& BREADTH ## FirstSearch_Body::prev( const int& i ) const { assert( i < m_V ); return m_prev[i]; } \ \ template \ int BREADTH ## FirstSearch_Body::Next() \ { \ \ if( m_next.empty() ){ \ \ return -1; \ \ } \ \ const int i_curr = m_next.front(); \ m_next.pop_front(); \ list edge = e( i_curr ); \ \ while( ! edge.empty() ){ \ \ const int& i = edge.front(); \ bool& found_i = found( i ); \ \ if( ! found_i ){ \ \ m_next.PUSH( i ); \ m_prev[i] = i_curr; \ found_i = true; \ \ } \ \ edge.pop_front(); \ \ } \ \ return i_curr; \ \ } \ \ template E(const int&)> inline list BREADTH ## FirstSearch::e( const int& t ) { return E( t ); } \ \ template E(const int&)> void BREADTH ## FirstConnectedComponentSearch( const int& V , int ( &cc_num )[V_max] , int& count ) \ { \ \ BREADTH ## FirstSearch bfs{ V }; \ count = 0; \ \ for( int i = 0 ; i < V ; i++ ){ \ \ cc_num[i] = -1; \ \ } \ \ for( int i = 0 ; i < V ; i++ ){ \ \ if( cc_num[i] == -1 ){ \ \ bfs.Shift( i ); \ int j = bfs.Next(); \ \ while( j != -1 ? cc_num[j] == -1 : false ){ \ \ cc_num[j] = count; \ j = bfs.Next(); \ \ } \ \ count++; \ \ } \ \ } \ \ return; \ \ } \ DECLARATION_OF_FIRST_SEARCH( Breadth ); DEFINITION_OF_FIRST_SEARCH( Breadth , push_back ); 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; list e[bound_N*2]; inline list E( const int& i ) { return e[i]; } int MAIN() { UNTIE; SET_ASSERT( N , 2 , bound_N ); SET_ASSERT( M , 1 , bound_M ); assert( M / ( N - 1 ) <= N ); 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 ); e[i].push_back( j + b * N ); e[j + b * N].push_back( i ); e[i + N].push_back( j + ( 1 - b ) * N ); e[j + ( 1 - b ) * N].push_back( i + N ); } int connected_component_num[bound_N*2]; int total_connected_component_num; BreadthFirstConnectedComponentSearch( N * 2 , connected_component_num , total_connected_component_num ); int count_chosen = 0; int chosen_connected_component_num[bound_N*2] = {}; FOR( i , 0 , N ){ int& connected_component_num_i = connected_component_num[i]; int& connected_component_num_i_N = connected_component_num[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 ){ int& connected_component_num_i = connected_component_num[i]; if( ( chosen_connected_component_num[connected_component_num_i] == 1 ) == non_flip ){ cout << i + 1 << " \n"[--count_chosen==0]; } } QUIT; }