TONG HOP

//Bài 1: Duyệt đồ thị 
//RONG
#include<stdio.h>
//Graph
typedef struct {
	int A[20][20];
	int n; //So luong dinh
}Graph;

void init_graph(Graph *pG, int n) {
	int i, j;
	pG->n=n;
	for(i=1; i<=n; i++) {
		for(j=1; j<=n; j++)
			pG->A[i][j]=0;	
	}
}

void add_edge(Graph *pG, int x, int y) {
	pG->A[x][y]=1;
	pG->A[y][x]=1;
}

//Kiem tra lang gieng x, y phai lang gieng khong?
int adjecent(Graph *pG, int x, int y) {
	return pG->A[x][y];
}

void print_graph(Graph *pG) {
	int i, j;
	for(i=1; i<=pG->n; i++) {
		for(j=1; j<=pG->n; j++) 
			printf("%d ", pG->A[i][j]);
		printf("\n");
	}
}

//Queue//
typedef struct {
	int data[100];
	int front, rear;
} Queue;
void make_null_queue(Queue* Q) {
	Q->front = 0;
	Q->rear = -1;
}
//Dua phan tu vap cuoi hang doi
void push(Queue* Q, int x) {
	Q->rear++;
	Q->data[Q->rear] = x;
}
//Xem phan tu dau hang doi
int top(Queue* Q) {
	return Q->data[Q->front];
}
void pop(Queue* Q) {
	Q->front++;
}
int empty(Queue* Q) {
	return Q->front > Q->rear;
}

//BFS
int mark[100];
void BFS_x(Graph *G, int s) {
	Queue Q;
	make_null_queue(&Q);
	push(&Q, s);
	while(!empty(&Q)) {
		int u=top(&Q); pop(&Q);
		if(mark[u]!=0)
			continue;
		printf("%d\n", u);
		mark[u]=1;
		int v;         
		for(v=1; v<=G->n; v++) {
			if(adjecent(G, u, v))
				push(&Q,v);
		}
	}
}

void BFS(Graph *G) {
	int i;
	for(i=1; i<=G->n; i++) 
		mark[i]=0;
	BFS_x(G, 1);
	for(i=1; i<=G->n; i++)
		if(mark[i]==0) {
			BFS_x(G, i);
		}
}
int main() {
	//freopen("dt.txt", "r", stdin);
	int i, j, m, n, u, v;
	Graph G;	
	scanf("%d%d", &n, &m);
	init_graph(&G, n);
	for(i=0; i<=m; i++) {
		scanf("%d%d", &u, &v);
		add_edge(&G, u, v);
	}
	//int mark[100];
	for(j=1; j<=G.n; j++)
		mark[j]=0;
	//print_graph(&G);
	BFS(&G);
	return 0;
}

//SAU
#include<stdio.h>
//Graph
typedef struct {
	int A[20][20];
	int n; //So luong dinh
}Graph;

void init_graph(Graph *pG, int n) {
	int i, j;
	pG->n=n;
	for(i=1; i<=n; i++) {
		for(j=1; j<=n; j++)
			pG->A[i][j]=0;	
	}
}

void add_edge(Graph *pG, int x, int y) {
	pG->A[x][y]=1;
	pG->A[y][x]=1;
}

//Kiem tra lang gieng x, y phai lang gieng khong?
int adjecent(Graph *pG, int x, int y) {
	return pG->A[x][y];
}

void print_graph(Graph *pG) {
	int i, j;
	for(i=1; i<=pG->n; i++) {
		for(j=1; j<=pG->n; j++) 
			printf("%d ", pG->A[i][j]);
		printf("\n");
	}
}

//Stack
typedef struct {
	int data[100];
	int size;
} Stack;
void make_null_stack(Stack* S) {
	S->size = 0;
}
void push(Stack* S, int x) {
	S->data[S->size] = x;
	S->size++;
}
int top(Stack* S) {
	return S->data[S->size-1];
}
void pop(Stack* S) {
	S->size--;
}
int empty(Stack* S) {
	return S->size == 0;
}

//DFS
int mark[100];
void DFS_x(Graph *G, int s) {
	Stack S;
	make_null_stack(&S);
	
	push(&S, s);
	
	while(!empty(&S)) {
		int u=top(&S); pop(&S);
		if(mark[u]!=0) {
			continue;
		}
		printf("%d\n", u);
		mark[u]=1;
		int v;
		for(v=1; v<=G->n; v++) {
			if(adjecent(G, u, v))
				push(&S, v);
		}
	}
}

void DFS(Graph *G) {
	int i;
	for(i=1; i<=G->n; i++) 
		mark[i]=0;
	DFS_x(G, 1);
	for(i=1; i<=G->n; i++)
		if(mark[i]==0) {
			DFS_x(G, i);
		}
}
int main() {
	//freopen("dt.txt", "r", stdin);
	int i, j, m, n, u, v;
	Graph G;	
	scanf("%d%d", &n, &m);
	init_graph(&G, n);
	for(i=0; i<=m; i++) {
		scanf("%d%d", &u, &v);
		add_edge(&G, u, v);
	}
	//int mark[100];
	for(j=1; j<=G.n; j++)
		mark[j]=0;
	//print_graph(&G);
	DFS(&G);
	return 0;
}


//DEQUY-vohuong
#include<stdio.h>
//Graph
typedef struct {
	int A[20][20];
	int n; //So luong dinh
}Graph;

void init_graph(Graph *pG, int n) {
	int i, j;
	pG->n=n;
	for(i=1; i<=n; i++) {
		for(j=1; j<=n; j++)
			pG->A[i][j]=0;	
	}
}

void add_edge(Graph *pG, int x, int y) {
	pG->A[x][y]=1;
	pG->A[y][x]=1;
}

//Kiem tra lang gieng x, y phai lang gieng khong?
int adjecent(Graph *pG, int x, int y) {
	return pG->A[x][y];
}

void print_graph(Graph *pG) {
	int i, j;
	for(i=1; i<=pG->n; i++) {
		for(j=1; j<=pG->n; j++) 
			printf("%d ", pG->A[i][j]);
		printf("\n");
	}
}


//DFS
int mark[100];
void DQ_x(Graph *G, int s) {
	if(mark[s]) return ;
	printf("%d\n", s);
	mark[s]=1;
	int v;
	for(v=1; v<=G->n; v++) 
		if(adjecent(G, s, v)) 
			DQ_x(G, v);
}

void DQ(Graph *G) {
	int i;
	for(i=1; i<=G->n; i++) 
		mark[i]=0;
	DQ_x(G, 1);
	for(i=1; i<=G->n; i++)
		if(mark[i]==0) {
			DQ_x(G, i);
		}
}
int main() {
	//freopen("dt.txt", "r", stdin);
	int i, j, m, n, u, v;
	Graph G;	
	scanf("%d%d", &n, &m);
	init_graph(&G, n);
	for(i=0; i<=m; i++) {
		scanf("%d%d", &u, &v);
		add_edge(&G, u, v);
	}
	//int mark[100];
	for(j=1; j<=G.n; j++)
		mark[j]=0;
	//print_graph(&G);
	DQ(&G);
	return 0;
}

//DUNG CAY-RONG
#include<stdio.h>

//Graph
typedef struct {
	int A[20][20];
	int n; //So luong dinh
}Graph;

void init_graph(Graph *pG, int n) {
	int i, j;
	pG->n=n;
	for(i=1; i<=n; i++) {
		for(j=1; j<=n; j++)
			pG->A[i][j]=0;	
	}
}

void add_edge(Graph *pG, int x, int y) {
	pG->A[x][y]=1;
	pG->A[y][x]=1;
}

//Kiem tra lang gieng x, y phai lang gieng khong?
int adjecent(Graph *pG, int x, int y) {
	return pG->A[x][y];
}

void print_graph(Graph *pG) {
	int i, j;
	for(i=1; i<=pG->n; i++) {
		for(j=1; j<=pG->n; j++) 
			printf("%d ", pG->A[i][j]);
		printf("\n");
	}
}

//Queue
typedef struct {
	int u, p;
}ElementType;
typedef struct {
	ElementType data[100];
	int front, rear;
} Queue;
void make_null_queue(Queue* Q) {
	Q->front = 0;
	Q->rear = -1;
}
//Dua phan tu vap cuoi hang doi = enqueue
void push(Queue* Q, ElementType pair) {
	Q->rear++;
	Q->data[Q->rear].u = pair.u;
	Q->data[Q->rear].p = pair.p;
}
//Xem phan tu dau hang doi = front
ElementType top(Queue* Q) {
	return Q->data[Q->front];
}
//dequeue xóa ph?n tu dau hang doi
void pop(Queue* Q) {
	Q->front++;
}
int empty(Queue* Q) {
	return Q->front > Q->rear;
}

//BFS
int mark[100];
int parent[100];
void BFS_x(Graph *G, int s) {
	Queue Q;
	make_null_queue(&Q);
	
	ElementType pair;
	pair.u=s; pair.p=0;
	push(&Q, pair);
	
	while(!empty(&Q)) {
		ElementType pair=top(&Q); pop(&Q);
		int u=pair.u, p=pair.p;
		if(mark[u]!=0)
			continue;
			
//		printf("%d %d\n", u, parent[s]);
		mark[u]=1;
		parent[u]=p;
		
		int v;         
		for(v=1; v<=G->n; v++) {
			if(adjecent(G, u, v)) {
				ElementType pair;
				pair.u=v; pair.p=u;
				push(&Q, pair);
			}	
		}
	}
}

void BFS(Graph *G) {
	int i;
	for(i=1; i<=G->n; i++) 
		mark[i]=0;
	BFS_x(G, 1);
	for(i=1; i<=G->n; i++)
		if(mark[i]==0) {
			BFS_x(G, i);
		}
}

int main() {
	//freopen("dt.txt", "r", stdin);
	int i, j, m, n, u, v;
	Graph G;	
	scanf("%d%d", &n, &m);
	init_graph(&G, n);
	for(i=0; i<=m; i++) {
		scanf("%d%d", &u, &v);
		add_edge(&G, u, v);
	}
	//int mark[100];
	for(j=1; j<=G.n; j++)
		mark[j]=0;
	//print_graph(&G);
	BFS(&G);
	for(i = 1;i<=n;i++){
		printf("%d %d\n",i,parent[i]);
	}
	return 0;
}

//DUNG CAY_SAU
#include<stdio.h>

//Graph
typedef struct {
	int A[20][20];
	int n; //So luong dinh
}Graph;

void init_graph(Graph *pG, int n) {
	int i, j;
	pG->n=n;
	for(i=1; i<=n; i++) {
		for(j=1; j<=n; j++)
			pG->A[i][j]=0;	
	}
}

void add_edge(Graph *pG, int x, int y) {
	pG->A[x][y]=1;
	pG->A[y][x]=1;
}

//Kiem tra lang gieng x, y phai lang gieng khong?
int adjecent(Graph *pG, int x, int y) {
	return pG->A[x][y];
}

void print_graph(Graph *pG) {
	int i, j;
	for(i=1; i<=pG->n; i++) {
		for(j=1; j<=pG->n; j++) 
			printf("%d ", pG->A[i][j]);
		printf("\n");
	}
}

//Stack
typedef struct {
	int u, p;
}ElementType;
typedef struct {
	ElementType data[100];
	int size;
} Stack;
void make_null_stack(Stack* S) {
	S->size = 0;
}
void push(Stack* S, ElementType pair) {
	S->data[S->size].u = pair.u;
	S->data[S->size].p = pair.p;
	S->size++;
}
ElementType top(Stack* S) {
	return S->data[S->size-1];
}
void pop(Stack* S) {
	S->size--;
}
int empty(Stack* S) {
	return S->size == 0;
}

//BFS
int mark[100];
int parent[100];
void DFS_x(Graph *G, int s) {
	Stack S;
	make_null_stack(&S);
	
	ElementType pair;
	pair.u=s; pair.p=0;
	push(&S, pair);
	
	while(!empty(&S)) {
		ElementType pair=top(&S); pop(&S);
		int u=pair.u, p=pair.p;
		if(mark[u]!=0) {
			continue;
		}
	
		mark[u]=1;
		parent[u]=p;
		//printf("%d %d\n", u, parent[u]);
		int v;
		for(v=1; v<=G->n; v++) {
			if(adjecent(G, u, v)){
				ElementType pair;
				pair.u=v; pair.p=u;
				push(&S, pair);	
			}
		}
	}
}

void DFS(Graph *G) {
	int i;
	for(i=1; i<=G->n; i++) 
		mark[i]=0;
	DFS_x(G, 1);
	for(i=1; i<=G->n; i++)
		if(mark[i]==0) {
			DFS_x(G, i);
		}
}

int main() {
	//freopen("dt.txt", "r", stdin);
	int i, j, m, n, u, v;
	Graph G;	
	scanf("%d%d", &n, &m);
	init_graph(&G, n);
	for(i=0; i<=m; i++) {
		scanf("%d%d", &u, &v);
		add_edge(&G, u, v);
	}
	for(j=1; j<=G.n; j++)
		mark[j]=0;
	//print_graph(&G);
	DFS(&G);
	for(i = 1;i<=n;i++){
		printf("%d %d\n",i,parent[i]);
	}
	return 0;
}

//DUNG CAY_DEQUY
#include<stdio.h>

//Graph
typedef struct {
	int A[20][20];
	int n; //So luong dinh
}Graph;

void init_graph(Graph *pG, int n) {
	int i, j;
	pG->n=n;
	for(i=1; i<=n; i++) {
		for(j=1; j<=n; j++)
			pG->A[i][j]=0;	
	}
}

void add_edge(Graph *pG, int x, int y) {
	pG->A[x][y]=1;
	pG->A[y][x]=1;
}

//Kiem tra lang gieng x, y phai lang gieng khong?
int adjecent(Graph *pG, int x, int y) {
	return pG->A[x][y];
}

void print_graph(Graph *pG) {
	int i, j;
	for(i=1; i<=pG->n; i++) {
		for(j=1; j<=pG->n; j++) 
			printf("%d ", pG->A[i][j]);
		printf("\n");
	}
}

//Stack
typedef struct {
	int u, p;
}ElementType;
typedef struct {
	ElementType data[100];
	int size;
} Stack;
void make_null_stack(Stack* S) {
	S->size = 0;
}
void push(Stack* S, ElementType pair) {
	S->data[S->size].u = pair.u;
	S->data[S->size].p = pair.p;
	S->size++;
}
ElementType top(Stack* S) {
	return S->data[S->size-1];
}
void pop(Stack* S) {
	S->size--;
}
int empty(Stack* S) {
	return S->size == 0;
}

//BFS
int mark[100];
int parent[100];
void DFS_x(Graph *G, int u, int p) {
//	Stack S;
//	make_null_stack(&S);
//	
//	ElementType pair;
//	pair.u=s; pair.p=0;
//	push(&S, pair);
//	
//	while(!empty(&S)) {
//		ElementType pair=top(&S); pop(&S);
//		int u=pair.u, p=pair.p;
//		if(mark[u]!=0) {
//			continue;
//		}
//	
//		mark[u]=1;
//		parent[u]=p;
//		printf("%d %d\n", u, parent[u]);
//		int v;
//		for(v=1; v<=G->n; v++) {
//			if(adjecent(G, u, v)){
//				ElementType pair;
//				pair.u=v; pair.p=u;
//				push(&S, pair);	
//			}
//		}
//	}
	if(mark[u] != 0) return;
	mark[u]=1;
	parent[u]=p;
	
	int v;
	for(v=1; v<=G->n; v++) {
		if(adjecent(G, u, v) && mark[v]==0) {
			DFS_x(G, v, u);
		}
	}
}

void DFS(Graph *G) {
	int i;
	for(i=1; i<=G->n; i++) 
		mark[i]=0;
	DFS_x(G, 1, 0);
	for(i=1; i<=G->n; i++)
		if(mark[i]==0) {
			DFS_x(G, i, 0);
		}
}

int main() {
	//freopen("dt.txt", "r", stdin);
	int i, j, m, n, u, v;
	Graph G;	
	scanf("%d%d", &n, &m);
	init_graph(&G, n);
	for(i=0; i<=m; i++) {
		scanf("%d%d", &u, &v);
		add_edge(&G, u, v);
	}
	for(j=1; j<=G.n; j++)
		mark[j]=0;
	//print_graph(&G);
	DFS(&G);
	for(i = 1;i<=n;i++){
		printf("%d %d\n",i,parent[i]);
	}
	return 0;
}

//CHUA DAO
#include<stdio.h>
//Graph
typedef struct {
	int A[20][20];
	int n; //So luong dinh
}Graph;

void init_graph(Graph *pG, int n) {
	int i, j;
	pG->n=n;
	for(i=1; i<=n; i++) {
		for(j=1; j<=n; j++)
			pG->A[i][j]=0;	
	}
}

void add_edge(Graph *pG, int x, int y) {
	pG->A[x][y]=1;
	pG->A[y][x]=1;
}
//Kiem tra lang gieng x, y phai lang gieng khong?
int adjecent(Graph *pG, int x, int y) {
	return pG->A[x][y];
}

void print_graph(Graph *pG) {
	int i, j;
	for(i=1; i<=pG->n; i++) {
		for(j=1; j<=pG->n; j++) 
			printf("%d ", pG->A[i][j]);
		printf("\n");
	}
}
//Queue//
typedef struct {
	int data[100];
	int front, rear;
} Queue;
void make_null_queue(Queue* Q) {
	Q->front = 0;
	Q->rear = -1;
}
//Dua phan tu vap cuoi hang doi
void push(Queue* Q, int x) {
	Q->rear++;
	Q->data[Q->rear] = x;
}
//Xem phan tu dau hang doi
int top(Queue* Q) {
	return Q->data[Q->front];
}
void pop(Queue* Q) {
	Q->front++;
}
int empty(Queue* Q) {
	return Q->front > Q->rear;
}

//BFS
int mark[100];
void BFS_x(Graph *G, int s) {
	Queue Q;
	make_null_queue(&Q);
	push(&Q, s);
	while(!empty(&Q)) {
		int u=top(&Q); pop(&Q);
		if(mark[u]!=0)
			continue;
	//	printf("%d\n", u);
		mark[u]=1;
		int v;         
		for(v=1; v<=G->n; v++) {
			if(adjecent(G, u, v))
				push(&Q,v);
		}
	}
}
int connected(Graph *pG) {
	int u;
	for(u=1; u<=pG->n; u++) 
		mark[u]=0;
	BFS_x(pG, 1);
	
	for(u=1; u<=pG->n; u++) 
		if(mark[u]==0) 
			return 0;
	return 1;
}
int main() {
	//freopen("dt.txt", "r", stdin);
	int i, m, n, u, v;
	Graph G;	
	scanf("%d%d", &n, &m);
	init_graph(&G, n);
	for(i=0; i<=m; i++) {
		scanf("%d%d", &u, &v);
		add_edge(&G, u, v);
	}
	int check = connected(&G);
	if(check) printf("YES");
	else printf("NO");
}

//TAY DU KY
#include<stdio.h>
//Graph
typedef struct {
	int A[20][20];
	int n; //So luong dinh
}Graph;

void init_graph(Graph *pG, int n) {
	int i, j;
	pG->n=n;
	for(i=1; i<=n; i++) {
		for(j=1; j<=n; j++)
			pG->A[i][j]=0;	
	}
}

void add_edge(Graph *pG, int x, int y) {
	pG->A[x][y]=1;
	pG->A[y][x]=1;
}
//Kiem tra lang gieng x, y phai lang gieng khong?
int adjecent(Graph *pG, int x, int y) {
	return pG->A[x][y];
}

void print_graph(Graph *pG) {
	int i, j;
	for(i=1; i<=pG->n; i++) {
		for(j=1; j<=pG->n; j++) 
			printf("%d ", pG->A[i][j]);
		printf("\n");
	}
}
//Queue//
typedef struct {
	int data[100];
	int front, rear;
} Queue;
void make_null_queue(Queue* Q) {
	Q->front = 0;
	Q->rear = -1;
}
//Dua phan tu vap cuoi hang doi
void push(Queue* Q, int x) {
	Q->rear++;
	Q->data[Q->rear] = x;
}
//Xem phan tu dau hang doi
int top(Queue* Q) {
	return Q->data[Q->front];
}
void pop(Queue* Q) {
	Q->front++;
}
int empty(Queue* Q) {
	return Q->front > Q->rear;
}

//BFS
int mark[100];
void BFS_x(Graph *G, int s) {
	Queue Q;
	make_null_queue(&Q);
	push(&Q, s);
	while(!empty(&Q)) {
		int u=top(&Q); pop(&Q);
		if(mark[u]!=0)
			continue;
	//	printf("%d\n", u);
		mark[u]=1;
		int v;         
		for(v=1; v<=G->n; v++) {
			if(adjecent(G, u, v))
				push(&Q,v);
		}
	}
}
int connected(Graph *pG) {
	int u;
	for(u=1; u<=pG->n; u++) 
		mark[u]=0;
	BFS_x(pG, 1);
	
	for(u=1; u<=pG->n; u++) 
		if(mark[u]==0) 
			return 0;
	return 1;
}
int main() {
	//freopen("dt.txt", "r", stdin);
	int i, m, n, u, v;
	Graph G;	
	scanf("%d%d", &n, &m);
	init_graph(&G, n);
	for(i=0; i<=m; i++) {
		scanf("%d%d", &u, &v);
		add_edge(&G, u, v);
	}
	int check = connected(&G);
	if(check) printf("DUOC");
	else printf("KHONG");
}

//CHUA CHU TRINH KHONG
#include<stdio.h>
typedef struct{
	int n,m;
	int A[100][100];
}Graph;
void initG(Graph *G, int n){
	G->n=n;
	int i,j;
	for(i=1;i<=G->n;i++){
		for(j=1;j<=n;j++){
			G->A[i][j]=0;
		}
	}
}
void addedge(Graph *G, int x, int y){
	if(x!=y){
	G->A[x][y]=1;
	G->A[y][x]=1;
	}
	else G->A[x][x]+=2;
}

typedef struct{
	int size;
	int L[100];
}List;
void makenullL(List *L){
	L->size=0;
}
void pushL(List *L, int x){
	L->L[L->size]=x;
	L->size++;
}

typedef struct{
	int S[100];
	int size;
}Stack;
void makenullS(Stack *S){
	S->size=0;
}
int topS(Stack *S){
	return S->S[S->size-1];
}
void popS(Stack *S){
	S->size--;
}
void pushS(Stack *S, int x){
	S->S[S->size]=x;
	S->size++;
}
int emptyS(Stack *S){
	return S->size==0;
}


void inMT(Graph *G){
	int i,j;
	for(i=1;i<=G->n;i++){
		printf("%d ",i);
		for(j=1;j<=G->n;j++){
			printf("%d ",G->A[i][j]);
		}
		printf("\n");
	}
}
List neighbour(Graph *G,int x){
	List L;
	makenullL(&L);
	int i;
	for(i=0;i<=G->n;i++){
		if(G->A[x][i]==1 )
			pushL(&L,i);
	}
	return L;
}

int color[100],cycle;
#define while 0
#define black 1
#define gray 2
void dfs(Graph *G,int x,int par){
	color[x]=gray;
	int j;
	List L=neighbour(G,x);
	for(j=1;j<=L.size;j++){
		int y=L.L[j-1];
		if(y==par)continue;
		if(color[y]==gray){
			cycle=1;
			return;
		}
		if(color[y]==while)dfs(G,y,x);
	}
	color[x]=black;
}
int contains(Graph *G){
	int i;
	for(i=1;i<=G->n;i++){
		color[i]=while;
	}
	cycle=0;
	for(i=1;i<=G->n;i++){
		if(color[i]==while) dfs(G,i,0);
	}
	return cycle;
}


int main(){
 
	Graph G;
	int n, m, u, v, e;
	scanf("%d%d", &n, &m);
	initG(&G, n);
	
	for (e = 0; e < m; e++) {
		scanf("%d %d", &u, &v);
		addedge(&G, u, v);
	}
	if(contains(&G)==0)printf("NO");
	else printf("YES");
    return 0;
}

//CHUA CHU TRINH KHONG, CO KHUYEN
#include<stdio.h>
typedef struct{
	int n,m;
	int A[100][100];
}Graph;
void initG(Graph *G, int n){
	G->n=n;
	int i,j;
	for(i=1;i<=G->n;i++){
		for(j=1;j<=n;j++){
			G->A[i][j]=0;
		}
	}
}
void addedge(Graph *G, int x, int y){
	if(x!=y){
	G->A[x][y]++;
	G->A[y][x]++;
	}
	else G->A[x][x]+=2;
}

typedef struct{
	int size;
	int L[100];
}List;
void makenullL(List *L){
	L->size=0;
}
void pushL(List *L, int x){
	L->L[L->size]=x;
	L->size++;
}

typedef struct{
	int S[100];
	int size;
}Stack;
void makenullS(Stack *S){
	S->size=0;
}
int topS(Stack *S){
	return S->S[S->size-1];
}
void popS(Stack *S){
	S->size--;
}
void pushS(Stack *S, int x){
	S->S[S->size]=x;
	S->size++;
}
int emptyS(Stack *S){
	return S->size==0;
}


void inMT(Graph *G){
	int i,j;
	for(i=1;i<=G->n;i++){
		for(j=1;j<=G->n;j++){
			printf("%d ",G->A[i][j]);
		}
		printf("\n");
	}
}
List neighbour(Graph *G,int x){
	List L;
	makenullL(&L);
	int i,j;
	for(i=0;i<=G->n;i++){
		for(j=1;j<=G->A[x][i];j++){
			pushL(&L,i);
		}
	}
	return L;
}
int KTtrungL(List *L){
	int i,j,tmp=0;
	for(i=0;i<L->size-1;i++){
		for(j=i+1;j<L->size;j++){
			if(L->L[i]==L->L[j]) tmp=1;
		}
	}
	return tmp;
}
int color[100],cycle;
#define while 0
#define black 1
#define gray 2
void dfs(Graph *G,int x,int par){
	color[x]=gray;
	int j;
	List L=neighbour(G,x);
	if(KTtrungL(&L)==1){
		cycle=1;
		return;
	}
	for(j=1;j<=L.size;j++){
		int y=L.L[j-1];
		if(y==par)continue;
		if(color[y]==gray){
			cycle=1;
			return;
		}
		if(color[y]==while)dfs(G,y,x);
	}
	color[x]=black;
}
int contains(Graph *G){
	int i;
	for(i=1;i<=G->n;i++){
		color[i]=while;
	}
	cycle=0;
	for(i=1;i<=G->n;i++){
		if(color[i]==while) dfs(G,i,0);
	}
	return cycle;
}


int main(){
 
	Graph G;
	int n, m, u, v, e;
	scanf("%d%d", &n, &m);
	initG(&G, n);
	
	for (e = 0; e < m; e++) {
		scanf("%d %d", &u, &v);
		addedge(&G, u, v);
	}
//	inMT(&G);
	if(contains(&G)==0)printf("NO");
	else printf("YES");
    return 0;
}

//HADDOCK
#include<stdio.h>
//Graph
typedef struct {
	int A[20][20];
	int n; //So luong dinh
}Graph;

void init_graph(Graph *pG, int n) {
	int i, j;
	pG->n=n;
	for(i=1; i<=n; i++) {
		for(j=1; j<=n; j++)
			pG->A[i][j]=0;	
	}
}

void add_edge(Graph *pG, int x, int y) {
	pG->A[x][y]=1;
}

//Kiem tra lang gieng x, y phai lang gieng khong?
int adjecent(Graph *pG, int x, int y) {
	return pG->A[x][y];
}

void print_graph(Graph *pG) {
	int i, j;
	for(i=1; i<=pG->n; i++) {
		for(j=1; j<=pG->n; j++) 
			printf("%d ", pG->A[i][j]);
		printf("\n");
	}
}

//Stack
typedef struct {
	int data[100];
	int size;
} Stack;
void make_null_stack(Stack* S) {
	S->size = 0;
}
void push(Stack* S, int x) {
	S->data[S->size] = x;
	S->size++;
}
int top(Stack* S) {
	return S->data[S->size-1];
}
void pop(Stack* S) {
	S->size--;
}
int empty(Stack* S) {
	return S->size == 0;
}

//DFS
#define WHITE 0
#define GRAY 1
#define BLACK 2
int color[100];
int has_circle;
void DFS_x(Graph *G, int s) {
	color[s]=GRAY;
	int v;
	for(v=1; v<=G->n; v++) 
	if(adjecent(G, s, v)) {
		if(color[v]==WHITE)
			DFS_x(G, v);
		else if(color[v]==GRAY) 
			has_circle=1;
	}
	color[s]=BLACK;
}
int main() {
	//freopen("dt.txt", "r", stdin);
	int i, j, m, n, u, v;
	Graph G;	
	scanf("%d%d", &n, &m);
	init_graph(&G, n);
	for(i=0; i<=m; i++) {
		scanf("%d%d", &u, &v);
		add_edge(&G, u, v);
	}
	for(i=0; i<=G.n; i++) {
		color[u]=WHITE;
	}
	has_circle=0;
	for(j=0; j<=G.n; j++) 
		if(color[j]==WHITE)
			DFS_x(&G, j);
	
	if(has_circle) printf("NO");
		else printf("YES");
	return 0;
}

//CHIA DOI BONG
#include<stdio.h>
#define NOCO 0
#define BLUE 1
#define RED 2

//Graph
typedef struct {
	int A[20][20];
	int n; //So luong dinh
}Graph;

void init_graph(Graph *pG, int n) {
	int i, j;
	pG->n=n;
	for(i=1; i<=n; i++) {
		for(j=1; j<=n; j++)
			pG->A[i][j]=0;	
	}
}

void add_edge(Graph *pG, int x, int y) {
	pG->A[x][y]=1;
	pG->A[y][x]=1;
}
//Kiem tra lang gieng x, y phai lang gieng khong?
int adjecent(Graph *pG, int x, int y) {
	return pG->A[x][y];
}

void print_graph(Graph *pG) {
	int i, j;
	for(i=1; i<=pG->n; i++) {
		for(j=1; j<=pG->n; j++) 
			printf("%d ", pG->A[i][j]);
		printf("\n");
	}
}

int color[100];
int conflict;
//int B[100];
void colorize(Graph *G, int u, int c) {
	
	color[u]=c;
	int v;
	for(v=1; v<=G->n; v++) {
		if(adjecent(G, u, v)) {
			if(color[v]==NOCO)
				colorize(G, v, 3-c);
			else if(color[v]==color[u])
				conflict=1;
		}
	}
	
}


int main() {
	//freopen("dt.txt", "r", stdin);
	int i, j, m, n, u, v;
	Graph G;	
	scanf("%d%d", &n, &m);
	init_graph(&G, n);
	for(i=1; i<=m; i++) {
		scanf("%d%d", &u, &v);
		add_edge(&G, u, v);
	}
	//print_graph(&G);
	for(i=1; i<=G.n; i++) {
		color[u]=NOCO;
	}
	conflict=0;
	for(j=1; j<=G.n; j++) 
		if(color[j]==NOCO)
			colorize(&G, j, 1);
	//printf("%d", color[1]);
	
	if(conflict!=1){
		for(i=1; i<=n; i++) {
			if(color[i]==BLUE) printf("%d ", i);
		}
		printf("\n");
		for(i=1; i<=n; i++) {
			if(color[i]==RED) printf("%d ", i);
		}
	} 
	else printf("IMPOSSIBLE");
	return 0;
}

//LIEN THONG MANH KHONG?
#include<stdio.h>
//Stack
typedef struct {
	int data[100];
	int size;
} Stack;
void make_null_stack(Stack* S) {
	S->size = 0;
}
void push(Stack* S, int x) {
	S->data[S->size] = x;
	S->size++;
}
int top(Stack* S) {
	return S->data[S->size-1];
}
void pop(Stack* S) {
	S->size--;
}
int empty(Stack* S) {
	return S->size == 0;
}
//Graph
typedef struct {
	int A[20][20];
	int n; //So luong dinh
}Graph;

void init_graph(Graph *pG, int n) {
	int i, j;
	pG->n=n;
	for(i=1; i<=n; i++) {
		for(j=1; j<=n; j++)
			pG->A[i][j]=0;	
	}
}

void add_edge(Graph *pG, int x, int y) {
	pG->A[x][y]=1;
}

int adjecent(Graph *pG, int x, int y) {
	return pG->A[x][y];
}

void print_graph(Graph *pG) {
	int i, j;
	for(i=1; i<=pG->n; i++) {
		for(j=1; j<=pG->n; j++) 
			printf("%d ", pG->A[i][j]);
		printf("\n");
	}
}

int num[100], min_num[100];
int k;
Stack S;
int on_stack[100];
int mark[100];

int min(int a, int b) {
	if(a<b) return a;
	if(a==b) return 0;
	else return b;
}
int check=0;
void SCC(Graph *pG, int u) {
	num[u]=min_num[u]=k; k++;
	push(&S, u);
	on_stack[u]=1;
	
	int v;
	for(v=1; v<=pG->n; v++) {
		if(adjecent(pG, u, v)) {
			if(num[v]<0) {
				SCC(pG, v);
				min_num[u]=min(min_num[u], min_num[v]);
			} else if(on_stack[v]) 
				min_num[u]=min(min_num[u], num[v]);
		}
	}
	
	if(num[u]==min_num[u]) {
		//printf("LTM, dinh %d la dinh khop \n", u);
		//check=1;
		check++;
		int w;
		do{
			w=top(&S);
			pop(&S);
			on_stack[w]=0;
		
		} while(w!=u);
	} 
}
int connected(Graph *pG) {
	int u;
	for(u=1; u<=pG->n; u++) {
	    num[u]=0;
		on_stack[u]=0;
	}
	make_null_stack(&S);
	for(u=1; u<=pG->n; u++)
		if(num[u]==0) 
			SCC(pG, u);
	return check;
}
int main() {
	//freopen("dt.txt", "r", stdin);
	int i, m, n, u, v;
	Graph G;	
	scanf("%d%d", &n, &m);
	init_graph(&G, n);
	for(i=0; i<=m; i++) {
		scanf("%d%d", &u, &v);
		add_edge(&G, u, v);
	}
	//print_graph(&G);
	for(i=1; i<=G.n; i++) 
		num[i]=-1;
	k=1;
	make_null_stack(&S);
	
	for(i=1; i<G.n; i++)
		if(num[i]==-1) 
			SCC(&G, i);
	
	//printf("%d\n",check );
	if(check==1) printf("unconnected");
	else printf("strong connected");
	
	return 0;
}

//DEM BO PHAN LTM
#include<stdio.h>
//Stack
typedef struct {
	int data[100];
	int size;
} Stack;
void make_null_stack(Stack* S) {
	S->size = 0;
}
void push(Stack* S, int x) {
	S->data[S->size] = x;
	S->size++;
}
int top(Stack* S) {
	return S->data[S->size-1];
}
void pop(Stack* S) {
	S->size--;
}
int empty(Stack* S) {
	return S->size == 0;
}
//Graph
typedef struct {
	int A[20][20];
	int n; //So luong dinh
}Graph;

void init_graph(Graph *pG, int n) {
	int i, j;
	pG->n=n;
	for(i=1; i<=n; i++) {
		for(j=1; j<=n; j++)
			pG->A[i][j]=0;	
	}
}

void add_edge(Graph *pG, int x, int y) {
	pG->A[x][y]=1;
}

int adjecent(Graph *pG, int x, int y) {
	return pG->A[x][y];
}

void print_graph(Graph *pG) {
	int i, j;
	for(i=1; i<=pG->n; i++) {
		for(j=1; j<=pG->n; j++) 
			printf("%d ", pG->A[i][j]);
		printf("\n");
	}
}

int num[100], min_num[100];
int k;
Stack S;
int on_stack[100];
int mark[100];

int min(int a, int b) {
	if(a<b) return a;
	if(a==b) return 0;
	else return b;
}
int check=0;
void SCC(Graph *pG, int u) {
	num[u]=min_num[u]=k; k++;
	push(&S, u);
	on_stack[u]=1;
	
	int v;
	for(v=1; v<=pG->n; v++) {
		if(adjecent(pG, u, v)) {
			if(num[v]<0) {
				SCC(pG, v);
				min_num[u]=min(min_num[u], min_num[v]);
			} else if(on_stack[v]) 
				min_num[u]=min(min_num[u], num[v]);
		}
	}
	
	if(num[u]==min_num[u]) {
		//printf("LTM, dinh %d la dinh khop \n", u);
		//check=1;
		check++;
		int w;
		do{
			w=top(&S);
			pop(&S);
			on_stack[w]=0;
		
		} while(w!=u);
	} 
}
int connected(Graph *pG) {
	int u;
	for(u=1; u<=pG->n; u++) {
	    num[u]=-1;
		on_stack[u]=0;
	}
	make_null_stack(&S);
	for(u=1; u<=pG->n; u++)
		if(num[u]==-1) 
			SCC(pG, u);
	return check;
}
int main() {
	//freopen("dt1.txt", "r", stdin);
	int i, m, n, u, v;
	Graph G;	
	scanf("%d%d", &n, &m);
	init_graph(&G, n);
	for(i=0; i<=m; i++) {
		scanf("%d%d", &u, &v);
		add_edge(&G, u, v);
	}
	//print_graph(&G);
	for(i=1; i<=G.n; i++) 
		num[i]=-1;
	k=1;
	make_null_stack(&S);
	
	for(i=1; i<=G.n; i++)
		if(num[i]==-1) 
			SCC(&G, i);
	
	printf("%d",connected(&G)+1);	
	return 0;
}

//COME AND GO
#include<stdio.h>
//Graph
typedef struct {
	int A[20][20];
	int n; //So luong dinh
}Graph;

void init_graph(Graph *pG, int n) {
	int i, j;
	pG->n=n;
	for(i=1; i<=n; i++) {
		for(j=1; j<=n; j++)
			pG->A[i][j]=0;	
	}
}

void add_edge(Graph *pG, int x, int y, int e) {
	if(e==1) 
		pG->A[x][y]=1;
	else if(e==2) {
		pG->A[x][y]=1;
		pG->A[y][x]=1;
	}
}

int adjecent(Graph *pG, int x, int y) {
	return pG->A[x][y];
}

void print_graph(Graph *pG) {
	int i, j;
	for(i=1; i<=pG->n; i++) {
		for(j=1; j<=pG->n; j++) 
			printf("%d ", pG->A[i][j]);
		printf("\n");
	}
}

//Stack
typedef struct {
	int data[100];
	int size;
} Stack;
void make_null_stack(Stack* S) {
	S->size = 0;
}
void push(Stack* S, int x) {
	S->data[S->size] = x;
	S->size++;
}
int top(Stack* S) {
	return S->data[S->size-1];
}
void pop(Stack* S) {
	S->size--;
}
int empty(Stack* S) {
	return S->size == 0;
}

int min(int x,int y){
	return x<y ? x:y;
}
int check;
int num[100], min_num[100];
int k;
Stack S;
int on_stack[100];

void SCC(Graph *pG, int u) {
	num[u]=min_num[u]=k; k++;
	push(&S, u);
	on_stack[u]=1;
	
	int v;
	for(v=1; v<=pG->n; v++) {
		if(adjecent(pG, u, v)) {
			if(num[v]<0) {
				SCC(pG, v);
				min_num[u]=min(min_num[u], min_num[v]);
			} else if(on_stack[v]) 
				min_num[u]=min(min_num[u], num[v]);
		}
	}
	
	if(num[u]==min_num[u]) {
	//	printf("LTM, dinh %d la dinh khop \n", u);
		check++;
		int w;
		do{
			w=top(&S);
			pop(&S);
			on_stack[w]=0;
		
		} while(w!=u);
	} 
}
int connected(Graph *pG) {
	int u;
	for(u=1; u<=pG->n; u++) {
	    num[u]=0;
		on_stack[u]=0;
	}
	
	make_null_stack(&S);
	for(u=1; u<=pG->n; u++)
		if(num[u]==0) 
			SCC(pG, u);
	return check;
}
int main() {
	//freopen("dt3.txt", "r", stdin);
	int i, m, n, u, v, e;
	Graph G;	
	scanf("%d%d", &n, &m);
	init_graph(&G, n);
	for(i=0; i<=m; i++) {
		scanf("%d%d%d", &u, &v, &e);
		add_edge(&G, u, v, e);
	}
	//print_graph(&G);
	for(i=1; i<=G.n; i++) 
		num[i]=-1;
	k=1;
	make_null_stack(&S);
	for(i=1; i<=G.n; i++)
		if(num[i]==-1) 
			SCC(&G, i);
	
	//printf("%d\n",check);
	if(check==1) printf("OKIE");
	else printf("NO");
	
	return 0;
}