시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 2581 1090 944 44.009%

문제

상근이는 자신의 결혼식에 학교 동기 중 자신의 친구와 친구의 친구를 초대하기로 했다. 상근이의 동기는 모두 N명이고, 이 학생들의 학번은 모두 1부터 N까지이다. 상근이의 학번은 1이다.

상근이는 동기들의 친구 관계를 모두 조사한 리스트를 가지고 있다. 이 리스트를 바탕으로 결혼식에 초대할 사람의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 상근이의 동기의 수 n (2 ≤ n ≤ 500)이 주어진다. 둘째 줄에는 리스트의 길이 m (1 ≤ m ≤ 10000)이 주어진다. 다음 줄부터 m개 줄에는 친구 관계 ai bi가 주어진다. (1 ≤ ai < bi ≤ n) ai와 bi가 친구라는 뜻이며, bi와 ai도 친구관계이다. 

출력

첫째 줄에 상근이의 결혼식에 초대하는 동기의 수를 출력한다.

예제 입력 1

6
5
1 2
1 3
3 4
2 3
4 5

예제 출력 1

3

힌트

2와 3은 상근이의 친구이다. 또, 3과 4는 친구이기 때문에, 4는 상근이의 친구의 친구이다. 5와 6은 친구도 아니고, 친구의 친구도 아니다. 따라서 2,3,4 3명의 친구를 결혼식에 초대한다.

W3sicHJvYmxlbV9pZCI6IjU1NjciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjYjBcdWQ2M2NcdWMyZGQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM3OTBcdWMyZTBcdWM3NTggXHVhY2IwXHVkNjNjXHVjMmRkXHVjNWQwIFx1ZDU1OVx1YWQ1MCBcdWIzZDlcdWFlMzAgXHVjOTExIFx1Yzc5MFx1YzJlMFx1Yzc1OCBcdWNlNWNcdWFkNmNcdWM2NDAgXHVjZTVjXHVhZDZjXHVjNzU4IFx1Y2U1Y1x1YWQ2Y1x1Yjk3YyBcdWNkMDhcdWIzMDBcdWQ1NThcdWFlMzBcdWI4NWMgXHVkNTg4XHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWM3NTggXHViM2Q5XHVhZTMwXHViMjk0IFx1YmFhOFx1YjQ1MCBOXHViYTg1XHVjNzc0XHVhY2UwLCBcdWM3NzQgXHVkNTU5XHVjMGRkXHViNGU0XHVjNzU4IFx1ZDU1OVx1YmM4OFx1Yzc0MCBcdWJhYThcdWI0NTAgMVx1YmQ4MFx1ZDEzMCBOXHVhZTRjXHVjOWMwXHVjNzc0XHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWM3NTggXHVkNTU5XHViYzg4XHVjNzQwIDFcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWIzZDlcdWFlMzBcdWI0ZTRcdWM3NTggXHVjZTVjXHVhZDZjIFx1YWQwMFx1YWNjNFx1Yjk3YyBcdWJhYThcdWI0NTAgXHVjODcwXHVjMGFjXHVkNTVjIFx1YjlhY1x1YzJhNFx1ZDJiOFx1Yjk3YyBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWM3NzQgXHViOWFjXHVjMmE0XHVkMmI4XHViOTdjIFx1YmMxNFx1ZDBkNVx1YzczY1x1Yjg1YyBcdWFjYjBcdWQ2M2NcdWMyZGRcdWM1ZDAgXHVjZDA4XHViMzAwXHVkNTYwIFx1YzBhY1x1Yjc4Y1x1Yzc1OCBcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzBjMVx1YWRmY1x1Yzc3NFx1Yzc1OCBcdWIzZDlcdWFlMzBcdWM3NTggXHVjMjE4IG4gKDIgJmxlOyBuICZsZTsgNTAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViOWFjXHVjMmE0XHVkMmI4XHVjNzU4IFx1YWUzOFx1Yzc3NCBtICgxICZsZTsgbSAmbGU7IDEwMDAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBcdWM5MDRcdWJkODBcdWQxMzAgbVx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjZTVjXHVhZDZjIFx1YWQwMFx1YWNjNCBhPHN1Yj5pPFwvc3ViPiBiPHN1Yj5pPFwvc3ViPlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgYTxzdWI+aTxcL3N1Yj4gJmx0OyBiPHN1Yj5pPFwvc3ViPiAmbGU7IG4pIGE8c3ViPmk8XC9zdWI+XHVjNjQwIGI8c3ViPmk8XC9zdWI+XHVhYzAwIFx1Y2U1Y1x1YWQ2Y1x1Yjc3Y1x1YjI5NCBcdWI3M2JcdWM3NzRcdWJhNzAsIGI8c3ViPmk8XC9zdWI+XHVjNjQwIGE8c3ViPmk8XC9zdWI+XHViM2M0IFx1Y2U1Y1x1YWQ2Y1x1YWQwMFx1YWNjNFx1Yzc3NFx1YjJlNC4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzBjMVx1YWRmY1x1Yzc3NFx1Yzc1OCBcdWFjYjBcdWQ2M2NcdWMyZGRcdWM1ZDAgXHVjZDA4XHViMzAwXHVkNTU4XHViMjk0IFx1YjNkOVx1YWUzMFx1Yzc1OCBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD4yXHVjNjQwIDNcdWM3NDAgXHVjMGMxXHVhZGZjXHVjNzc0XHVjNzU4IFx1Y2U1Y1x1YWQ2Y1x1Yzc3NFx1YjJlNC4gXHViNjEwLCAzXHVhY2ZjIDRcdWIyOTQgXHVjZTVjXHVhZDZjXHVjNzc0XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgNFx1YjI5NCBcdWMwYzFcdWFkZmNcdWM3NzRcdWM3NTggXHVjZTVjXHVhZDZjXHVjNzU4IFx1Y2U1Y1x1YWQ2Y1x1Yzc3NFx1YjJlNC4gNVx1YzY0MCA2XHVjNzQwIFx1Y2U1Y1x1YWQ2Y1x1YjNjNCBcdWM1NDRcdWIyYzhcdWFjZTAsIFx1Y2U1Y1x1YWQ2Y1x1Yzc1OCBcdWNlNWNcdWFkNmNcdWIzYzQgXHVjNTQ0XHViMmM4XHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMgMiwzLDQgM1x1YmE4NVx1Yzc1OCBcdWNlNWNcdWFkNmNcdWI5N2MgXHVhY2IwXHVkNjNjXHVjMmRkXHVjNWQwIFx1Y2QwOFx1YjMwMFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjU1NjciLCJwcm9ibGVtX2xhbmciOiIyIiwidGl0bGUiOiJcdTMwZDFcdTMwZmNcdTMwYzZcdTMwYTNcdTMwZmMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1MzA0Mlx1MzA2YVx1MzA1Zlx1MzA2Zlx1MzBhZlx1MzBlYVx1MzBiOVx1MzBkZVx1MzBiOVx1MzBkMVx1MzBmY1x1MzBjNlx1MzBhM1x1MzBmY1x1MzA2Ylx1NWI2Nlx1NjgyMVx1NTE4NVx1MzA2ZVx1ODFlYVx1NTIwNlx1MzA2ZVx1NTNjYlx1OTA1NFx1MzA2OFx1ZmYwY1x1ODFlYVx1NTIwNlx1MzA2ZVx1NTNjYlx1OTA1NFx1MzA2ZVx1NTNjYlx1OTA1NFx1MzA5Mlx1NjJkYlx1NWY4NVx1MzA1OVx1MzA4Ylx1MzA1M1x1MzA2OFx1MzA2Ylx1MzA1N1x1MzA1Zlx1ZmYwZSBcdTMwNDJcdTMwNmFcdTMwNWZcdTMwNmVcdTkwMWFcdTMwNDZcdTViNjZcdTY4MjFcdTMwNmVcdTc1MWZcdTVmOTJcdTY1NzBcdTMwNmYgbiBcdTRlYmFcdTMwNjdcdTMwNDJcdTMwOGFcdWZmMGNcdTMwNWRcdTMwOGNcdTMwNWVcdTMwOGNcdTMwNmVcdTc1MWZcdTVmOTJcdTMwNmJcdTMwNmYgMSBcdTMwNGJcdTMwODkgbiBcdTMwN2VcdTMwNjdcdTMwNmVcdTc1NmFcdTUzZjdcdTMwNGNcdTUyNzJcdTMwOGFcdTYzMmZcdTMwODlcdTMwOGNcdTMwNjZcdTMwNDRcdTMwOGJcdWZmMGUgXHUzMDQyXHUzMDZhXHUzMDVmXHUzMDZlXHU3NTZhXHU1M2Y3XHUzMDZmIDEgXHUzMDY3XHUzMDQyXHUzMDhiXHVmZjBlIFx1MzA0Mlx1MzA2YVx1MzA1Zlx1MzA2ZVx1NjI0Ylx1NTE0M1x1MzA2Ylx1MzA2Zlx1ZmYwY1x1OGFiMFx1MzA2OFx1OGFiMFx1MzA0Y1x1NTNjYlx1OTA1NFx1MzA2N1x1MzA0Mlx1MzA4Ylx1MzA0Ylx1MzA5Mlx1OGExOFx1MzA1N1x1MzA1Zlx1MzBlYVx1MzBiOVx1MzBjOFx1MzA0Y1x1MzA0Mlx1MzA4Ylx1ZmYwZSBcdTMwNTNcdTMwNmVcdTMwZWFcdTMwYjlcdTMwYzhcdTMwOTJcdTMwODJcdTMwNjhcdTMwNmJcdWZmMGMgXHUzMDQyXHUzMDZhXHUzMDVmXHUzMDRjXHUzMGFmXHUzMGVhXHUzMGI5XHUzMGRlXHUzMGI5XHUzMGQxXHUzMGZjXHUzMGM2XHUzMGEzXHUzMGZjXHUzMDZiXHU2MmRiXHU1Zjg1XHUzMDU5XHUzMDhiXHU3NTFmXHU1ZjkyXHU2NTcwXHUzMDkyXHU2YzQyXHUzMDgxXHUzMDhiXHUzMGQ3XHUzMGVkXHUzMGIwXHUzMGU5XHUzMGUwXHUzMDkyXHU0ZjVjXHU2MjEwXHUzMDViXHUzMDg4XHVmZjBlPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHU1MTY1XHU1MjliXHUzMDZlMSBcdTg4NGNcdTc2ZWVcdTMwNmJcdTMwNmZcdTViNjZcdTY4MjFcdTMwNmVcdTc1MWZcdTVmOTJcdTY1NzAgbiBcdWZmMDgyIFx1MjI2NiBuIFx1MjI2NiA1MDBcdWZmMDlcdTMwNGNcdWZmMGMgMiBcdTg4NGNcdTc2ZWVcdTMwNmJcdTMwNmZcdTMwZWFcdTMwYjlcdTMwYzhcdTMwNmVcdTk1NzdcdTMwNTUgbSBcdWZmMDgxIFx1MjI2NiBtIFx1MjI2NiAxMDAwMFx1ZmYwOVx1MzA0Y1x1NjZmOFx1MzA0Ylx1MzA4Y1x1MzA2Nlx1MzA0NFx1MzA4Ylx1ZmYwZSBcdTUxNjVcdTUyOWJcdTMwNmZcdTUxNjhcdTkwZThcdTMwNjcgMittIFx1ODg0Y1x1MzA0Ylx1MzA4OVx1MzA2YVx1MzA4Ylx1ZmYwZTIraSBcdTg4NGNcdTc2ZWVcdWZmMDgxIFx1MjI2NiBpIFx1MjI2NiBtXHVmZjA5XHUzMDZiXHUzMDZmIDIgXHUzMDY0XHUzMDZlXHU2NTc0XHU2NTcwIGE8c3ViPmk8XC9zdWI+IFx1MzA2OCBiPHN1Yj5pPFwvc3ViPiBcdWZmMDgxIFx1MjI2NiBhPHN1Yj5pPFwvc3ViPiBcdWZmMWMgYjxzdWI+aTxcL3N1Yj4gXHUyMjY2IG5cdWZmMDlcdTMwNGNcdTdhN2FcdTc2N2RcdTUzM2FcdTUyMDdcdTMwOGFcdTMwNjdcdTY2ZjhcdTMwNGJcdTMwOGNcdTMwNjZcdTMwNGFcdTMwOGFcdWZmMGNcdTc1NmFcdTUzZjcgYTxzdWI+aTxcL3N1Yj4gXHUzMDY4XHU3NTZhXHU1M2Y3IGI8c3ViPmk8XC9zdWI+IFx1MzA2ZVx1NzUxZlx1NWY5Mlx1MzA0Y1x1NTNjYlx1OTA1NFx1NTQwY1x1NThlYlx1MzA2N1x1MzA0Mlx1MzA4Ylx1MzA1M1x1MzA2OFx1MzA5Mlx1ODg2OFx1MzA1OVx1ZmYwZSBcdTUxNjVcdTUyOWJcdTMwNmUgMyBcdTg4NGNcdTc2ZWVcdTMwNGJcdTMwODkgMittIFx1ODg0Y1x1NzZlZVx1MzA2Ylx1MzA2Zlx1NTQwY1x1MzA1OFx1NTNjYlx1OTA1NFx1OTVhMlx1NGZjMlx1MzA5Mlx1ODg2OFx1MzA1OVx1ODg0Y1x1MzA0Y1x1OTFjZFx1ODkwN1x1MzA1N1x1MzA2Nlx1NzNmZVx1MzA4Y1x1MzA4Ylx1MzA1M1x1MzA2OFx1MzA2Zlx1MzA2YVx1MzA0NFx1ZmYwZTxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdTUxZmFcdTUyOWJcdTMwNmZcdWZmMGNcdTMwNDJcdTMwNmFcdTMwNWZcdTMwNGNcdTMwYWZcdTMwZWFcdTMwYjlcdTMwZGVcdTMwYjlcdTMwZDFcdTMwZmNcdTMwYzZcdTMwYTNcdTMwZmNcdTMwNmJcdTYyZGJcdTVmODVcdTMwNTlcdTMwOGJcdTc1MWZcdTVmOTJcdTY1NzBcdTMwNmVcdTMwN2ZcdTMwOTJcdTU0MmJcdTMwODAgMSBcdTg4NGNcdTMwNGJcdTMwODlcdTMwNmFcdTMwOGJcdWZmMGU8XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IjxwPlx1MzA0Mlx1MzA2YVx1MzA1Zlx1MzA2ZVx1NTNjYlx1OTA1NFx1MzA2Zlx1NzU2YVx1NTNmNyAyIFx1MzA2OFx1NzU2YVx1NTNmNyAzIFx1MzA2ZVx1NzUxZlx1NWY5Mlx1MzA2ZSAyIFx1NGViYVx1MzA2N1x1MzA0Mlx1MzA4Ylx1ZmYwZSBcdTMwN2VcdTMwNWZcdWZmMGNcdTc1NmFcdTUzZjcgMyBcdTMwNjhcdTc1NmFcdTUzZjcgNCBcdTMwNmVcdTc1MWZcdTVmOTJcdTMwNmZcdTUzY2JcdTkwNTRcdTU0MGNcdTU4ZWJcdTMwNjdcdTMwNDJcdTMwOGJcdTMwNmVcdTMwNjdcdWZmMGMgXHU3NTZhXHU1M2Y3IDQgXHUzMDZlXHU3NTFmXHU1ZjkyXHUzMDZmXHUzMDQyXHUzMDZhXHUzMDVmXHUzMDZlXHU1M2NiXHU5MDU0XHUzMDZlXHU1M2NiXHU5MDU0XHUzMDY3XHUzMDQyXHUzMDhiXHVmZjBlIFx1NzU2YVx1NTNmNyA1IFx1MzA2OFx1NzU2YVx1NTNmNyA2IFx1MzA2ZVx1NzUxZlx1NWY5Mlx1MzA2Zlx1MzA0Mlx1MzA2YVx1MzA1Zlx1MzA2ZVx1NTNjYlx1OTA1NFx1MzA2N1x1MzA4Mlx1MzA2YVx1MzA0Zlx1ZmYwY1x1MzA0Mlx1MzA2YVx1MzA1Zlx1MzA2ZVx1NTNjYlx1OTA1NFx1MzA2ZVx1NTNjYlx1OTA1NFx1MzA2N1x1MzA4Mlx1MzA2YVx1MzA0NFx1ZmYwZSBcdTMwNTdcdTMwNWZcdTMwNGNcdTMwNjNcdTMwNjZcdWZmMGNcdTMwNDJcdTMwNmFcdTMwNWZcdTMwNmZcdTc1NmFcdTUzZjcgMiwzLDQgXHUzMDZlIDMgXHU0ZWJhXHUzMDZlXHU3NTFmXHU1ZjkyXHUzMDkyXHUzMGFmXHUzMGVhXHUzMGI5XHUzMGRlXHUzMGI5XHUzMGQxXHUzMGZjXHUzMGM2XHUzMGEzXHUzMGZjXHUzMDZiXHU2MmRiXHU1Zjg1XHUzMDU5XHUzMDhiXHVmZjBlPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNzdjXHViY2Y4XHVjNWI0In1d

출처

Olympiad > 일본정보올림피아드 예선 > JOI 2010 예선 3번