#include using namespace std; typedef long long ll; typedef vector< int > vi; typedef vector< vi > vvi; typedef vector< ll > vl; typedef vector< vl > vvl; typedef pair< int, int > pii; typedef vector< pii > vp; typedef vector< double > vd; typedef vector< vd > vvd; typedef vector< string > vs; template< class T1, class T2 > int upmin( T1 &x, T2 v ){ if( x > v ){ x = v; return 1; } return 0; } template< class T1, class T2 > int upmax( T1 &x, T2 v ){ if( x < v ){ x = v; return 1; } return 0; } const int INF = 0x3f3f3f3f; int N, M; vi A, B; void init(){ cin >> N >> M; A = B = vi( M ); for( int i = 0; i < M; ++i ) cin >> A[ i ] >> B[ i ]; } vvi G; void preprocess(){ G = vvi( N ); for( int i = 0; i < M; ++i ) G[ A[ i ] - 1 ].emplace_back( B[ i ] - 1 ), G[ B[ i ] - 1 ].emplace_back( A[ i ] - 1 ); } void solve(){ vi col( N ); for( int t = 0; t < 1000; ++t ){ for( int i = 1; i < N; ++i ) col[ i ] = rand() % 4; vvi dp( 1 << 4, vi( N ) ); queue< tuple< int, int > > que; for( int u : G[ 0 ] ) dp[ 1 << col[ u ] ][ u ] = 1, que.emplace( 1 << col[ u ], u ); while( not que.empty() ){ int s, u; tie( s, u ) = que.front(); que.pop(); for( int v : G[ u ] ) if( v != 0 ) if( ~s & 1 << col[ v ] ) if( upmax( dp[ s | 1 << col[ v ] ][ v ], 1 ) ) que.emplace( s | 1 << col[ v ], v ); } for( int u : G[ 0 ] ) if( dp[ ( 1 << 4 ) - 1 ][ u ] ) cout << "YES" << endl, exit( 0 ); } cout << "NO" << endl; } signed main(){ ios::sync_with_stdio( 0 ); init(); preprocess(); solve(); return 0; }