P3043 [USACO12JAN] Bovine Alliance G

Bessie and her bovine pals from nearby farms have finally decided that they are going to start connecting their farms together by trails in an effort to form an alliance against the farmers. The cows in each of the N (1

* Line 1: Two space-separated integers N and M * Lines 2..1+M: Line i+1 describes the ith trail. Each line contains two space-separated integers u_i and v_i (1

* Line 1: A single line containing the number of assignments of trails to farms, taken modulo 1,000,000,007. If no assignment satisfies the above conditions output 0.

Note that there can be two trails between the same pair of farms. There are 6 possible assignments. Letting {a,b,c,d} mean that farm 1 builds trail a, farm 2 builds trail b, farm 3 builds trail c, and farm 4 builds trail d, the assignments are: ```plain {2, 3, 4, 5} {2, 3, 5, 4} {1, 3, 4, 5} {1, 3, 5, 4} {1, 2, 4, 5} {1, 2, 5, 4} ```