Migrated from Lutece 1436 成电网红卿学姐

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

众所周知，卿学姐是成电第一网红。电子科大有N个学生，他们都有着自己的初始性取向（喜欢男的or喜欢女的），电子科大有M场不同时期的演唱会，每个人都会选择两场演唱会观看。卿学姐每场演唱会可以选择参加演出或者不参加，由于卿学姐的特殊能力，电子科大的学生每看一次卿学姐的演出就会改变一次性取向。所以卿学姐想知道，她最少需要参加多少场演唱会才能让电子科大有相同兴趣的学生性取向都一样。（可怕的卿学姐！！），如果A和B有一场相同的演唱会，则两人有相同的兴趣，如果A和B，B和C有相同兴趣，则A和C有相同兴趣。

Input

第一行两个整数n(1≤n≤1000000)，m（2≤m≤100000）。

接下来n行，每行三个整数ai，bi,ci,（1≤ai≤m）,（1≤bi≤m），（ai≠bi）。表示第i个学生选择观看的两场演唱会。ci=1表示第i个学生初始性取向为喜欢男，ci=2表示第i个学生初始性取向为喜欢女。

Output

一个整数表示卿学姐最少需参加演出的演唱会场数，如果无法使有相同兴趣学生性取向都一样，则输出-1；

Samples

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

2

Resources

2016 UESTC Training for Graph Theory