Description

长大后的爱丽丝是一名记者，她来到永眠镇进行专题采访。永眠镇有 $n$ 座房子，由 $m$ 条双向道路连接，房子从 $1$ 到 $n$ 编号。爱丽丝事先对采访内容作了规划，在她的规划中，有些道路是必经道路，其他道路是可选道路。

爱丽丝不希望走重复的路，并且希望采访结束后回到起点。具体地，爱丽丝希望找到一条满足下列条件的回路：

• 回路从某个房子出发，经过若干条道路后再回到同一座房子；
• 一条道路不能重复经过（即使方向不同）；
• 每条必经道路恰好经过一次。

图可能有重边和自环，如果多条重边都是必经道路，那么符合要求的回路必须经过其中的每一条。

永眠镇的道路具有特殊的性质：

1. 必经道路连通所有的房子，即可以仅经过必经道路从任意一座房子到达任意另一座房子；
2. 不存在 $m$ 座房子，两个端点都在这 $m$ 座房子中的可选道路超过 $m$ 条。

想到可能不存在符合要求的回路，爱丽丝提前联系了永眠镇的祭司。祭司可以在任意两座房子之间打出特殊通道（即便这两座房子之间已经有道路连接），爱丽丝可以穿过特殊通道从一座房子到达另一座房子，同时特殊通道销毁。

爱丽丝想知道至少需要打出几条特殊通道。在特殊通道数量最少的基础上，爱丽丝还想知道符合要求的回路至少要经过几条可选道路。鉴于这个问题比较复杂，爱丽丝会指定其中一个问题，并希望你给出答案。

输入格式

输入的第一行包含四个整数 $c,type,n,m$，分别表示测试点编号，爱丽丝希望你回答的问题，以及房子和道路的数量。对于样例，$c$ 表示该样例与测试点 $c$ 拥有相同的限制条件。

如果 $type=1$，那么爱丽丝希望你告诉她至少需要打出几条特殊通道。如果 $type=2$，那么爱丽丝希望你告诉她在特殊通道数量最少的基础上，符合要求的回路至少要经过可选道路。

接下来的 $m$ 行每行包含三个整数 $u,v,w$，分别表示这条道路连接的两座房子以及这条道路的类型。如果 $w=1$，那么这条道路是必经道路。如果 $w=0$，那么这条道路是可选道路。

输出格式

输出一行一个整数，表示答案。