시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB194918713710444.517%

문제

상근이는 자신의 결혼식에 학교 동기 중 자신의 친구와 친구의 친구를 초대하기로 했다. 상근이의 동기는 모두 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

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

예제 출력 2

0

힌트

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

W3sicHJvYmxlbV9pZCI6IjU1NjciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjYjBcdWQ2M2NcdWMyZGQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM3OTBcdWMyZTBcdWM3NTggXHVhY2IwXHVkNjNjXHVjMmRkXHVjNWQwIFx1ZDU1OVx1YWQ1MCBcdWIzZDlcdWFlMzAgXHVjOTExIFx1Yzc5MFx1YzJlMFx1Yzc1OCBcdWNlNWNcdWFkNmNcdWM2NDAgXHVjZTVjXHVhZDZjXHVjNzU4IFx1Y2U1Y1x1YWQ2Y1x1Yjk3YyBcdWNkMDhcdWIzMDBcdWQ1NThcdWFlMzBcdWI4NWMgXHVkNTg4XHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWM3NTggXHViM2Q5XHVhZTMwXHViMjk0IFx1YmFhOFx1YjQ1MCBOXHViYTg1XHVjNzc0XHVhY2UwLCBcdWM3NzQgXHVkNTU5XHVjMGRkXHViNGU0XHVjNzU4IFx1ZDU1OVx1YmM4OFx1Yzc0MCBcdWJhYThcdWI0NTAgMVx1YmQ4MFx1ZDEzMCBOXHVhZTRjXHVjOWMwXHVjNzc0XHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWM3NTggXHVkNTU5XHViYzg4XHVjNzQwIDFcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWIzZDlcdWFlMzBcdWI0ZTRcdWM3NTggXHVjZTVjXHVhZDZjIFx1YWQwMFx1YWNjNFx1Yjk3YyBcdWJhYThcdWI0NTAgXHVjODcwXHVjMGFjXHVkNTVjIFx1YjlhY1x1YzJhNFx1ZDJiOFx1Yjk3YyBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWM3NzQgXHViOWFjXHVjMmE0XHVkMmI4XHViOTdjIFx1YmMxNFx1ZDBkNVx1YzczY1x1Yjg1YyBcdWFjYjBcdWQ2M2NcdWMyZGRcdWM1ZDAgXHVjZDA4XHViMzAwXHVkNTYwIFx1YzBhY1x1Yjc4Y1x1Yzc1OCBcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzBjMVx1YWRmY1x1Yzc3NFx1Yzc1OCBcdWIzZDlcdWFlMzBcdWM3NTggXHVjMjE4IG4gKDIgJmxlOyBuICZsZTsgNTAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViOWFjXHVjMmE0XHVkMmI4XHVjNzU4IFx1YWUzOFx1Yzc3NCBtICgxICZsZTsgbSAmbGU7IDEwMDAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBcdWM5MDRcdWJkODBcdWQxMzAgbVx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjZTVjXHVhZDZjIFx1YWQwMFx1YWNjNCBhPHN1Yj5pPFwvc3ViPiBiPHN1Yj5pPFwvc3ViPlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgYTxzdWI+aTxcL3N1Yj4gJmx0OyBiPHN1Yj5pPFwvc3ViPiAmbGU7IG4pIGE8c3ViPmk8XC9zdWI+XHVjNjQwIGI8c3ViPmk8XC9zdWI+XHVhYzAwIFx1Y2U1Y1x1YWQ2Y1x1Yjc3Y1x1YjI5NCBcdWI3M2JcdWM3NzRcdWJhNzAsIGI8c3ViPmk8XC9zdWI+XHVjNjQwIGE8c3ViPmk8XC9zdWI+XHViM2M0IFx1Y2U1Y1x1YWQ2Y1x1YWQwMFx1YWNjNFx1Yzc3NFx1YjJlNC4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzBjMVx1YWRmY1x1Yzc3NFx1Yzc1OCBcdWFjYjBcdWQ2M2NcdWMyZGRcdWM1ZDAgXHVjZDA4XHViMzAwXHVkNTU4XHViMjk0IFx1YjNkOVx1YWUzMFx1Yzc1OCBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWM2MDhcdWM4MWMgMVx1Yzc1OCBcdWFjYmRcdWM2YjAgMlx1YzY0MCAzXHVjNzQwIFx1YzBjMVx1YWRmY1x1Yzc3NFx1Yzc1OCBcdWNlNWNcdWFkNmNcdWM3NzRcdWIyZTQuIFx1YjYxMCwgM1x1YWNmYyA0XHViMjk0IFx1Y2U1Y1x1YWQ2Y1x1Yzc3NFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIDRcdWIyOTQgXHVjMGMxXHVhZGZjXHVjNzc0XHVjNzU4IFx1Y2U1Y1x1YWQ2Y1x1Yzc1OCBcdWNlNWNcdWFkNmNcdWM3NzRcdWIyZTQuIDVcdWM2NDAgNlx1Yzc0MCBcdWNlNWNcdWFkNmNcdWIzYzQgXHVjNTQ0XHViMmM4XHVhY2UwLCBcdWNlNWNcdWFkNmNcdWM3NTggXHVjZTVjXHVhZDZjXHViM2M0IFx1YzU0NFx1YjJjOFx1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjIDIsIDMsIDQgM1x1YmE4NVx1Yzc1OCBcdWNlNWNcdWFkNmNcdWI5N2MgXHVhY2IwXHVkNjNjXHVjMmRkXHVjNWQwIFx1Y2QwOFx1YjMwMFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjU1NjciLCJwcm9ibGVtX2xhbmciOiIyIiwidGl0bGUiOiJcdTMwZDFcdTMwZmNcdTMwYzZcdTMwYTNcdTMwZmMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1MzA0Mlx1MzA2YVx1MzA1Zlx1MzA2Zlx1MzBhZlx1MzBlYVx1MzBiOVx1MzBkZVx1MzBiOVx1MzBkMVx1MzBmY1x1MzBjNlx1MzBhM1x1MzBmY1x1MzA2Ylx1NWI2Nlx1NjgyMVx1NTE4NVx1MzA2ZVx1ODFlYVx1NTIwNlx1MzA2ZVx1NTNjYlx1OTA1NFx1MzA2OFx1ZmYwY1x1ODFlYVx1NTIwNlx1MzA2ZVx1NTNjYlx1OTA1NFx1MzA2ZVx1NTNjYlx1OTA1NFx1MzA5Mlx1NjJkYlx1NWY4NVx1MzA1OVx1MzA4Ylx1MzA1M1x1MzA2OFx1MzA2Ylx1MzA1N1x1MzA1Zlx1ZmYwZSBcdTMwNDJcdTMwNmFcdTMwNWZcdTMwNmVcdTkwMWFcdTMwNDZcdTViNjZcdTY4MjFcdTMwNmVcdTc1MWZcdTVmOTJcdTY1NzBcdTMwNmYgbiBcdTRlYmFcdTMwNjdcdTMwNDJcdTMwOGFcdWZmMGNcdTMwNWRcdTMwOGNcdTMwNWVcdTMwOGNcdTMwNmVcdTc1MWZcdTVmOTJcdTMwNmJcdTMwNmYgMSBcdTMwNGJcdTMwODkgbiBcdTMwN2VcdTMwNjdcdTMwNmVcdTc1NmFcdTUzZjdcdTMwNGNcdTUyNzJcdTMwOGFcdTYzMmZcdTMwODlcdTMwOGNcdTMwNjZcdTMwNDRcdTMwOGJcdWZmMGUgXHUzMDQyXHUzMDZhXHUzMDVmXHUzMDZlXHU3NTZhXHU1M2Y3XHUzMDZmIDEgXHUzMDY3XHUzMDQyXHUzMDhiXHVmZjBlIFx1MzA0Mlx1MzA2YVx1MzA1Zlx1MzA2ZVx1NjI0Ylx1NTE0M1x1MzA2Ylx1MzA2Zlx1ZmYwY1x1OGFiMFx1MzA2OFx1OGFiMFx1MzA0Y1x1NTNjYlx1OTA1NFx1MzA2N1x1MzA0Mlx1MzA4Ylx1MzA0Ylx1MzA5Mlx1OGExOFx1MzA1N1x1MzA1Zlx1MzBlYVx1MzBiOVx1MzBjOFx1MzA0Y1x1MzA0Mlx1MzA4Ylx1ZmYwZSBcdTMwNTNcdTMwNmVcdTMwZWFcdTMwYjlcdTMwYzhcdTMwOTJcdTMwODJcdTMwNjhcdTMwNmJcdWZmMGMgXHUzMDQyXHUzMDZhXHUzMDVmXHUzMDRjXHUzMGFmXHUzMGVhXHUzMGI5XHUzMGRlXHUzMGI5XHUzMGQxXHUzMGZjXHUzMGM2XHUzMGEzXHUzMGZjXHUzMDZiXHU2MmRiXHU1Zjg1XHUzMDU5XHUzMDhiXHU3NTFmXHU1ZjkyXHU2NTcwXHUzMDkyXHU2YzQyXHUzMDgxXHUzMDhiXHUzMGQ3XHUzMGVkXHUzMGIwXHUzMGU5XHUzMGUwXHUzMDkyXHU0ZjVjXHU2MjEwXHUzMDViXHUzMDg4XHVmZjBlPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdTUxNjVcdTUyOWJcdTMwNmUxIFx1ODg0Y1x1NzZlZVx1MzA2Ylx1MzA2Zlx1NWI2Nlx1NjgyMVx1MzA2ZVx1NzUxZlx1NWY5Mlx1NjU3MCBuIFx1ZmYwODIgXHUyMjY2IG4gXHUyMjY2IDUwMFx1ZmYwOVx1MzA0Y1x1ZmYwYyAyIFx1ODg0Y1x1NzZlZVx1MzA2Ylx1MzA2Zlx1MzBlYVx1MzBiOVx1MzBjOFx1MzA2ZVx1OTU3N1x1MzA1NSBtIFx1ZmYwODEgXHUyMjY2IG0gXHUyMjY2IDEwMDAwXHVmZjA5XHUzMDRjXHU2NmY4XHUzMDRiXHUzMDhjXHUzMDY2XHUzMDQ0XHUzMDhiXHVmZjBlIFx1NTE2NVx1NTI5Ylx1MzA2Zlx1NTE2OFx1OTBlOFx1MzA2NyAyK20gXHU4ODRjXHUzMDRiXHUzMDg5XHUzMDZhXHUzMDhiXHVmZjBlMitpIFx1ODg0Y1x1NzZlZVx1ZmYwODEgXHUyMjY2IGkgXHUyMjY2IG1cdWZmMDlcdTMwNmJcdTMwNmYgMiBcdTMwNjRcdTMwNmVcdTY1NzRcdTY1NzAgYTxzdWI+aTxcL3N1Yj4gXHUzMDY4IGI8c3ViPmk8XC9zdWI+IFx1ZmYwODEgXHUyMjY2IGE8c3ViPmk8XC9zdWI+IFx1ZmYxYyBiPHN1Yj5pPFwvc3ViPiBcdTIyNjYgblx1ZmYwOVx1MzA0Y1x1N2E3YVx1NzY3ZFx1NTMzYVx1NTIwN1x1MzA4YVx1MzA2N1x1NjZmOFx1MzA0Ylx1MzA4Y1x1MzA2Nlx1MzA0YVx1MzA4YVx1ZmYwY1x1NzU2YVx1NTNmNyBhPHN1Yj5pPFwvc3ViPiBcdTMwNjhcdTc1NmFcdTUzZjcgYjxzdWI+aTxcL3N1Yj4gXHUzMDZlXHU3NTFmXHU1ZjkyXHUzMDRjXHU1M2NiXHU5MDU0XHU1NDBjXHU1OGViXHUzMDY3XHUzMDQyXHUzMDhiXHUzMDUzXHUzMDY4XHUzMDkyXHU4ODY4XHUzMDU5XHVmZjBlIFx1NTE2NVx1NTI5Ylx1MzA2ZSAzIFx1ODg0Y1x1NzZlZVx1MzA0Ylx1MzA4OSAyK20gXHU4ODRjXHU3NmVlXHUzMDZiXHUzMDZmXHU1NDBjXHUzMDU4XHU1M2NiXHU5MDU0XHU5NWEyXHU0ZmMyXHUzMDkyXHU4ODY4XHUzMDU5XHU4ODRjXHUzMDRjXHU5MWNkXHU4OTA3XHUzMDU3XHUzMDY2XHU3M2ZlXHUzMDhjXHUzMDhiXHUzMDUzXHUzMDY4XHUzMDZmXHUzMDZhXHUzMDQ0XHVmZjBlPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHU1MWZhXHU1MjliXHUzMDZmXHVmZjBjXHUzMDQyXHUzMDZhXHUzMDVmXHUzMDRjXHUzMGFmXHUzMGVhXHUzMGI5XHUzMGRlXHUzMGI5XHUzMGQxXHUzMGZjXHUzMGM2XHUzMGEzXHUzMGZjXHUzMDZiXHU2MmRiXHU1Zjg1XHUzMDU5XHUzMDhiXHU3NTFmXHU1ZjkyXHU2NTcwXHUzMDZlXHUzMDdmXHUzMDkyXHU1NDJiXHUzMDgwIDEgXHU4ODRjXHUzMDRiXHUzMDg5XHUzMDZhXHUzMDhiXHVmZjBlPFwvcD5cclxuIiwiaGludCI6IjxwPlx1NTE2NVx1NTI5Ylx1NGY4YiAxIFx1MzA2Ylx1MzA0YVx1MzA0NFx1MzA2Nlx1ZmYwY1x1MzA0Mlx1MzA2YVx1MzA1Zlx1MzA2ZVx1NTNjYlx1OTA1NFx1MzA2Zlx1NzU2YVx1NTNmNyAyIFx1MzA2OFx1NzU2YVx1NTNmNyAzIFx1MzA2ZVx1NzUxZlx1NWY5Mlx1MzA2ZSAyIFx1NGViYVx1MzA2N1x1MzA0Mlx1MzA4Ylx1ZmYwZSBcdTMwN2VcdTMwNWZcdWZmMGNcdTc1NmFcdTUzZjcgMyBcdTMwNjhcdTc1NmFcdTUzZjcgNCBcdTMwNmVcdTc1MWZcdTVmOTJcdTMwNmZcdTUzY2JcdTkwNTRcdTU0MGNcdTU4ZWJcdTMwNjdcdTMwNDJcdTMwOGJcdTMwNmVcdTMwNjdcdWZmMGMgXHU3NTZhXHU1M2Y3IDQgXHUzMDZlXHU3NTFmXHU1ZjkyXHUzMDZmXHUzMDQyXHUzMDZhXHUzMDVmXHUzMDZlXHU1M2NiXHU5MDU0XHUzMDZlXHU1M2NiXHU5MDU0XHUzMDY3XHUzMDQyXHUzMDhiXHVmZjBlIFx1NzU2YVx1NTNmNyA1IFx1MzA2OFx1NzU2YVx1NTNmNyA2IFx1MzA2ZVx1NzUxZlx1NWY5Mlx1MzA2Zlx1MzA0Mlx1MzA2YVx1MzA1Zlx1MzA2ZVx1NTNjYlx1OTA1NFx1MzA2N1x1MzA4Mlx1MzA2YVx1MzA0Zlx1ZmYwY1x1MzA0Mlx1MzA2YVx1MzA1Zlx1MzA2ZVx1NTNjYlx1OTA1NFx1MzA2ZVx1NTNjYlx1OTA1NFx1MzA2N1x1MzA4Mlx1MzA2YVx1MzA0NFx1ZmYwZSBcdTMwNTdcdTMwNWZcdTMwNGNcdTMwNjNcdTMwNjZcdWZmMGNcdTMwNDJcdTMwNmFcdTMwNWZcdTMwNmZcdTc1NmFcdTUzZjcgMiwzLDQgXHUzMDZlIDMgXHU0ZWJhXHUzMDZlXHU3NTFmXHU1ZjkyXHUzMDkyXHUzMGFmXHUzMGVhXHUzMGI5XHUzMGRlXHUzMGI5XHUzMGQxXHUzMGZjXHUzMGM2XHUzMGEzXHUzMGZjXHUzMDZiXHU2MmRiXHU1Zjg1XHUzMDU5XHUzMDhiXHVmZjBlPFwvcD5cclxuXHJcbjxwPlx1NTE2NVx1NTI5Ylx1NGY4YiAyIFx1MzA2Ylx1MzA0YVx1MzA0NFx1MzA2Nlx1ZmYwY1x1MzA0Mlx1MzA2YVx1MzA1Zlx1MzA2Ylx1MzA2Zlx1NTNjYlx1OTA1NFx1MzA2Zlx1MzA0NFx1MzA2YVx1MzA0NFx1ZmYwZSBcdTMwNTdcdTMwNWZcdTMwNGNcdTMwNjNcdTMwNjZcdWZmMGNcdTMwNDJcdTMwNmFcdTMwNWZcdTMwNGNcdTMwYWZcdTMwZWFcdTMwYjlcdTMwZGVcdTMwYjlcdTMwZDFcdTMwZmNcdTMwYzZcdTMwYTNcdTMwZmNcdTMwNmJcdTYyZGJcdTVmODVcdTMwNTlcdTMwOGJcdTc1MWZcdTVmOTJcdTY1NzBcdTMwNmYgMCBcdTRlYmFcdTMwNjdcdTMwNDJcdTMwOGJcdWZmMGU8XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkphcGFuZXNlIn1d

출처

Olympiad > Japanese Olympiad in Informatics > Japanese Olympiad in Informatics Qualification Round > JOI 2009/2010 예선 3번