6861: BZOJ2861:双向边定向为单向边

Memory Limit:128 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

A国由N个城市、M条道路组成,两个城市之间,可能存在一条或多条道路。可能是单行道,也可能是双行道。现在你要把尽量多的双行道定向,改成单行道。并

且保证连通性不变。
所谓连通性不变,就是如果原本A城市可以到B城市。那么道路改造之后A仍然能够到B城市。


输入格式

第一行为两个整数N、M。以下M行,每行三个数:Xi,Yi,Bi。若Bi为1则表示存在一条Xi到Yi的单行道,Bi为2则表示存在一条连接Xi与Yi的双行道。


输出格式

仅一个数,为最多可以给多少个双行道定向。


样例输入

4 4
1 2 1
2 3 2
3 1 2
2 4 2

样例输出

 2

提示

【数据范围】
N<=100000 M<=200000
道路的两端保证连接着不同的城市。
 


题目来源

没有写明来源

加入题单

上一题 下一题 算法标签: