Một cuộc đua xe đạp đang được tổ chức trong một vùng đất xa xôi. Có ~N~ thị trấn trong vùng đất đó, được đánh số từ 1 đến ~N~. Có ~M~ con đường một chiều nối giữa các thị trấn. Cuộc đua sẽ bắt đầu ở thị trấn 1 và kết thúc ở thị trấn 2.

Có bao nhiêu cách khác nhau có thể thiết lập tuyến đường? Hai tuyến đường được coi là khác nhau nếu chúng không sử dụng chính xác các con đường giống nhau.

Input

Dòng đầu tiên của đầu vào chứa hai số nguyên ~N~ và ~M~ (~1 ≤ N ≤ 10,000~, ~1 ≤ M ≤ 100,000~), số lượng thị trấn và số đường.

Mỗi trong ~M~ dòng tiếp theo chứa hai số nguyên khác nhau ~A~ và ~B~, đại diện cho một con đường giữa các thị trấn ~A~ và ~B~.

Các thị trấn có thể được kết nối bởi nhiều hơn một con đường.

Output

In ra số lượng tuyến đường riêng biệt có thể thiết lập trên một dòng duy nhất. Nếu số đó có hơn chín chữ số, chỉ in ra chín chữ số cuối cùng của số đó. Nếu có vô số tuyến đường, in ra "inf".

Sample Input 1

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

Sample Output 1

3

Sample Input 2

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

Sample Output 2

inf