시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 404 56 48 21.053%

문제

1번부터 N번까지 번호가 매겨져 있는 N개의 마을과 마을을 연결하는 M개의 일방통행 도로로 이루어진 나라가 있다. 이 나라에서는 자전거 경주 대회를 개최하려고 한다. 경주는 1번 마을에서 시작해야 하고, 2번 마을에서 끝나야 한다.

자전거 경주를 개최할 수 있는 경로의 수는 총 몇 가지가 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 100,000)

다음 M개 줄에는 도로의 정보를 나타내는 A와 B가 주어진다. 이 정보는 A에서 B로 향하는 도로를 나타낸다.

마을은 하나 이상의 도로로 연결되어 있을 수도 있다.

출력

첫째 줄에 가능한 자전거 경주 대회 경로의 수를 출력한다. 수가 9자리를 넘어가는 경우에는 뒤의 9자리만 출력하면 된다. 만약, 경로의 수가 무한대인 경우에는 "inf"를 출력한다.

예제 입력 1

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

예제 출력 1

3
W3sicHJvYmxlbV9pZCI6IjMwNDQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3OTBcdWM4MDRcdWFjNzAgXHVhY2JkXHVjOGZjIFx1YzkwMFx1YmU0NFx1ZDU1OFx1YWUzMCIsImRlc2NyaXB0aW9uIjoiPHA+MVx1YmM4OFx1YmQ4MFx1ZDEzMCBOXHViYzg4XHVhZTRjXHVjOWMwIFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWI5ZTRcdWFjYThcdWM4MzggXHVjNzg4XHViMjk0IE5cdWFjMWNcdWM3NTggXHViOWM4XHVjNzQ0XHVhY2ZjIFx1YjljOFx1Yzc0NFx1Yzc0NCBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgTVx1YWMxY1x1Yzc1OCBcdWM3N2NcdWJjMjlcdWQxYjVcdWQ1ODkmbmJzcDtcdWIzYzRcdWI4NWNcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YjA5OFx1Yjc3Y1x1YWMwMCBcdWM3ODhcdWIyZTQuIFx1Yzc3NCBcdWIwOThcdWI3N2NcdWM1ZDBcdWMxMWNcdWIyOTQgXHVjNzkwXHVjODA0XHVhYzcwIFx1YWNiZFx1YzhmYyBcdWIzMDBcdWQ2OGNcdWI5N2MgXHVhYzFjXHVjZDVjXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVhY2JkXHVjOGZjXHViMjk0IDFcdWJjODggXHViOWM4XHVjNzQ0XHVjNWQwXHVjMTFjIFx1YzJkY1x1Yzc5MVx1ZDU3NFx1YzU3YyBcdWQ1NThcdWFjZTAsIDJcdWJjODggXHViOWM4XHVjNzQ0XHVjNWQwXHVjMTFjIFx1YjA1ZFx1YjA5OFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc5MFx1YzgwNFx1YWM3MCBcdWFjYmRcdWM4ZmNcdWI5N2MgXHVhYzFjXHVjZDVjXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhY2JkXHViODVjXHVjNzU4IFx1YzIxOFx1YjI5NCBcdWNkMWQgXHViYTg3IFx1YWMwMFx1YzljMFx1YWMwMCBcdWM3ODhcdWIyOTRcdWM5YzAgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIE5cdWFjZmMgTVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiAmbGU7IDEwLDAwMCwgMSAmbGU7IE0gJmxlOyAxMDAsMDAwKTxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgTVx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViM2M0XHViODVjXHVjNzU4IFx1YzgxNVx1YmNmNFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgQVx1YzY0MCBCXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0IFx1YzgxNVx1YmNmNFx1YjI5NCBBXHVjNWQwXHVjMTFjIEJcdWI4NWMgXHVkNWE1XHVkNTU4XHViMjk0IFx1YjNjNFx1Yjg1Y1x1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjljOFx1Yzc0NFx1Yzc0MCBcdWQ1NThcdWIwOTggXHVjNzc0XHVjMGMxXHVjNzU4IFx1YjNjNFx1Yjg1Y1x1Yjg1YyBcdWM1ZjBcdWFjYjBcdWI0MThcdWM1YjQgXHVjNzg4XHVjNzQ0IFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWFjMDBcdWIyYTVcdWQ1NWMgXHVjNzkwXHVjODA0XHVhYzcwIFx1YWNiZFx1YzhmYyBcdWIzMDBcdWQ2OGMgXHVhY2JkXHViODVjXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YzIxOFx1YWMwMCA5XHVjNzkwXHViOWFjXHViOTdjIFx1YjExOFx1YzViNFx1YWMwMFx1YjI5NCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHViNGE0XHVjNzU4IDlcdWM3OTBcdWI5YWNcdWI5Y2MgXHVjZDljXHViODI1XHVkNTU4XHViYTc0IFx1YjQxY1x1YjJlNC4gXHViOWNjXHVjNTdkLCBcdWFjYmRcdWI4NWNcdWM3NTggXHVjMjE4XHVhYzAwIFx1YmIzNFx1ZDU1Y1x1YjMwMFx1Yzc3OCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgJnF1b3Q7aW5mJnF1b3Q7XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzMDQ0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQklDSUtMSSIsImRlc2NyaXB0aW9uIjoiPHA+QSBiaWN5Y2xlIHJhY2UgaXMgYmVpbmcgb3JnYW5pemVkIGluIGEgbGFuZCBmYXIsIGZhciBhd2F5LiBUaGVyZSBhcmUgTiB0b3duIGluIHRoZSBsYW5kLCBudW1iZXJlZCAxIHRocm91Z2ggTi4gVGhlcmUgYXJlIGFsc28gTSBvbmUtd2F5IHJvYWRzIGJldHdlZW4gdGhlIHRvd25zLiBUaGUgcmFjZSB3aWxsIHN0YXJ0IGluIHRvd24gMSBhbmQgZW5kIGluIHRvd24gMi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+SG93IG1hbnkgZGlmZmVyZW50IHdheXMgY2FuIHRoZSByb3V0ZSBiZSBzZXQ/IFR3byByb3V0ZXMgYXJlIGNvbnNpZGVyZWQgZGlmZmVyZW50IGlmIHRoZXkgZG8gbm90IHVzZSB0aGUgZXhhY3Qgc2FtZSByb2Fkcy4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHR3byBpbnRlZ2VycyBOIGFuZCBNICgxICZsZTsgTiAmbGU7IDEwIDAwMCwgMSAmbGU7IE0gJmxlOyAxMDAgMDAwKSwgdGhlIG51bWJlciBvZiB0b3ducyBhbmQgcm9hZHMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIG5leHQgTSBsaW5lcyBjb250YWlucyB0d28gZGlmZmVyZW50IGludGVnZXJzIEEgYW5kIEIsIHJlcHJlc2VudGluZyBhIHJvYWQgYmV0d2VlbiB0b3ducyBBIGFuZCBCLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Ub3ducyBtYXkgYmUgY29ubmVjdGVkIGJ5IG1vcmUgdGhhbiBvbmUgcm9hZC4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgdGhlIG51bWJlciBvZiBkaXN0aW5jdCByb3V0ZXMgdGhhdCBjYW4gYmUgc2V0IG9uIGEgc2luZ2xlIGxpbmUuIElmIHRoYXQgbnVtYmVyIGhhcyBtb3JlIHRoYW4gbmluZSBkaWdpdHMsIG91dHB1dCBvbmx5IHRoZSBsYXN0IG5pbmUgZGlnaXRzIG9mIHRoZSBudW1iZXIuIElmIHRoZXJlIGFyZSBpbmZpbml0ZWx5IG1hbnkgcm91dGVzLCBvdXRwdXQgJnF1b3Q7aW5mJnF1b3Q7LiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Contest > Croatian Open Competition in Informatics > COCI 2006/2007 > Contest #3 5번

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: hyunynim