시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 333 47 40 20.942%

문제

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
W3sicHJvYmxlbV9pZCI6IjMwNDQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3OTBcdWM4MDRcdWFjNzAgXHVhY2JkXHVjOGZjIFx1YzkwMFx1YmU0NFx1ZDU1OFx1YWUzMCIsImRlc2NyaXB0aW9uIjoiXHJcbjxwPlxyXG5cdDFcdWJjODhcdWJkODBcdWQxMzAgTlx1YmM4OFx1YWU0Y1x1YzljMCBcdWJjODhcdWQ2MzhcdWFjMDAgXHViOWU0XHVhY2E4XHVjODM4IFx1Yzc4OFx1YjI5NCBOXHVhYzFjXHVjNzU4IFx1YjljOFx1Yzc0NFx1YWNmYyBcdWI5YzhcdWM3NDRcdWM3NDQgXHVjNWYwXHVhY2IwXHVkNTU4XHViMjk0IE1cdWFjMWNcdWM3NTggXHVjNzdjXHViYzI5XHVkMWI1XHVkNTZkIFx1YjNjNFx1Yjg1Y1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHViMDk4XHViNzdjXHVhYzAwIFx1Yzc4OFx1YjJlNC4gXHVjNzc0IFx1YjA5OFx1Yjc3Y1x1YzVkMFx1YzExY1x1YjI5NCBcdWM3OTBcdWM4MDRcdWFjNzAgXHVhY2JkXHVjOGZjIFx1YjMwMFx1ZDY4Y1x1Yjk3YyBcdWFjMWNcdWNkNWNcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWFjYmRcdWM4ZmNcdWIyOTQgMVx1YmM4OCBcdWI5YzhcdWM3NDRcdWM1ZDBcdWMxMWMgXHVjMmRjXHVjNzkxXHVkNTc0XHVjNTdjIFx1ZDU1OFx1YWNlMCwgMlx1YmM4OCBcdWI5YzhcdWM3NDRcdWM1ZDBcdWMxMWMgXHViMDVkXHViMDk4XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjNzkwXHVjODA0XHVhYzcwIFx1YWNiZFx1YzhmY1x1Yjk3YyBcdWFjMWNcdWNkNWNcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjYmRcdWI4NWNcdWM3NTggXHVjMjE4XHViMjk0IFx1Y2QxZCBcdWJhODcgXHVhYzAwXHVjOWMwXHVhYzAwIFx1Yzc4OFx1YjI5NFx1YzljMCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IlxyXG48cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIE5cdWFjZmMgTVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiAmbGU7IDEwLDAwMCwgMSAmbGU7IE0gJmxlOyAxMDAsMDAwKTxcL3A+XHJcblxyXG48cD5cclxuXHRcdWIyZTRcdWM3NGMgTVx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViM2M0XHViODVjXHVjNzU4IFx1YzgxNVx1YmNmNFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgQVx1YzY0MCBCXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0IFx1YzgxNVx1YmNmNFx1YjI5NCBBXHVjNWQwXHVjMTFjIEJcdWI4NWMgXHVkNWE1XHVkNTU4XHViMjk0IFx1YjNjNFx1Yjg1Y1x1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YjljOFx1Yzc0NFx1Yzc0MCBcdWQ1NThcdWIwOTggXHVjNzc0XHVjMGMxXHVjNzU4IFx1YjNjNFx1Yjg1Y1x1Yjg1YyBcdWM1ZjBcdWFjYjBcdWI0MThcdWM1YjQgXHVjNzg4XHVjNzQ0IFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWFjMDBcdWIyYTVcdWQ1NWMgXHVjNzkwXHVjODA0XHVhYzcwIFx1YWNiZFx1YzhmYyBcdWIzMDBcdWQ2OGMgXHVhY2JkXHViODVjXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YzIxOFx1YWMwMCA5XHVjNzkwXHViOWFjXHViOTdjIFx1YjExOFx1YzViNFx1YWMwMFx1YjI5NCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHViNGE0XHVjNzU4IDlcdWM3OTBcdWI5YWNcdWI5Y2MgXHVjZDljXHViODI1XHVkNTU4XHViYTc0IFx1YjQxY1x1YjJlNC4gXHViOWNjXHVjNTdkLCBcdWFjYmRcdWI4NWNcdWM3NTggXHVjMjE4XHVhYzAwIFx1YmIzNFx1ZDU1Y1x1YjMwMFx1Yzc3OCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgJnF1b3Q7aW5mJnF1b3Q7XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzMDQ0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQklDSUtMSSIsImRlc2NyaXB0aW9uIjoiPHA+QSBiaWN5Y2xlIHJhY2UgaXMgYmVpbmcgb3JnYW5pemVkIGluIGEgbGFuZCBmYXIsIGZhciBhd2F5LiBUaGVyZSBhcmUgTiB0b3duIGluIHRoZSBsYW5kLCBudW1iZXJlZCAxIHRocm91Z2ggTi4gVGhlcmUgYXJlIGFsc28gTSBvbmUtd2F5IHJvYWRzIGJldHdlZW4gdGhlIHRvd25zLiBUaGUgcmFjZSB3aWxsIHN0YXJ0IGluIHRvd24gMSBhbmQgZW5kIGluIHRvd24gMi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+SG93IG1hbnkgZGlmZmVyZW50IHdheXMgY2FuIHRoZSByb3V0ZSBiZSBzZXQ/IFR3byByb3V0ZXMgYXJlIGNvbnNpZGVyZWQgZGlmZmVyZW50IGlmIHRoZXkgZG8gbm90IHVzZSB0aGUgZXhhY3Qgc2FtZSByb2Fkcy4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHR3byBpbnRlZ2VycyBOIGFuZCBNICgxICZsZTsgTiAmbGU7IDEwIDAwMCwgMSAmbGU7IE0gJmxlOyAxMDAgMDAwKSwgdGhlIG51bWJlciBvZiB0b3ducyBhbmQgcm9hZHMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIG5leHQgTSBsaW5lcyBjb250YWlucyB0d28gZGlmZmVyZW50IGludGVnZXJzIEEgYW5kIEIsIHJlcHJlc2VudGluZyBhIHJvYWQgYmV0d2VlbiB0b3ducyBBIGFuZCBCLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Ub3ducyBtYXkgYmUgY29ubmVjdGVkIGJ5IG1vcmUgdGhhbiBvbmUgcm9hZC4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgdGhlIG51bWJlciBvZiBkaXN0aW5jdCByb3V0ZXMgdGhhdCBjYW4gYmUgc2V0IG9uIGEgc2luZ2xlIGxpbmUuIElmIHRoYXQgbnVtYmVyIGhhcyBtb3JlIHRoYW4gbmluZSBkaWdpdHMsIG91dHB1dCBvbmx5IHRoZSBsYXN0IG5pbmUgZGlnaXRzIG9mIHRoZSBudW1iZXIuIElmIHRoZXJlIGFyZSBpbmZpbml0ZWx5IG1hbnkgcm91dGVzLCBvdXRwdXQgJnF1b3Q7aW5mJnF1b3Q7LiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==