assignment-3

There are N men standing in a row.We can assign one of three color  R(Red),G(Green) and Black(B) to each man.
  Unfortunately,at the end we forgot that what color we assigned to each man.But we remember a list of K relationships between pairs of men.
Example 1st man and 2nd man has same color and 3rd man and 5th having different color.
  Your tast is to calculate number of possible assignmnet of colors to men.

INPUT:

Line 1:N and K. 
  Lines 2..1+K:
  Each line describes the relationship between a pair of men A and B (1 ≤ A,B ≤ N, A != B). 
  It is either of the form "1 A B", meaning that A and B have the same color, or "0 A B", meaning that A and B have different colors.

OUTPUT:

Print an Integer indicating number of possible assignmnet of colors to men.
If given information is contradictory then print 0.

Constraints:

1 ≤ N ≤ 15

1 ≤ k ≤ 50

SAMPLE INPUT
4 2 
1 1 2
0 1 3

SAMPLE OUTPUT
18

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions: