Time Limit: 2 Seconds
Memory Limit: 65536 KB
There are many anime that are about "love triangles": Alice loves Bob, and Charlie loves Bob as well, but Alice hates Charlie. You are thinking about an anime which has n characters. The characters are labeled from 1 to n. Every pair of two characters can either mutually love each other or mutually hate each other (there is no neutral state).
You hate bad triangles (A-B are in love but B-C hate each other and A-C hate each other), and you also hate it when nobody is in love. So, considering any three characters, you will be happy if exactly two pair is in love (A and B hate each other, and C loves both A and B), or if all three pairs are in love (A loves B, B loves C, C loves A).
You are given a list of m known relationships in the anime. You know for sure that certain pairs love each other, and certain pairs hate each other. You're wondering how many triangles can make you happy while you can fill in the remaining relationships. Two triangles are considered the same if two triangles have the same characters and the relationships between them are the same. Print this count modulo 999983.
The input file contains multiple test cases.
The first line contains two integers n,m(1≤ n ≤ 100000, 0≤ m ≤ 100000), indicating the number of characters and the number of known relationships between them.
The following m lines contains three integers x,y,z(1≤ x,y ≤ n, 0≤z≤ 1) indicating the relationships between x and y, if z = 0, x hates y. If z = 1, x loves y.