4274 - 纸杯藏球

题目描述

课间休息时,小 H 和小 K 喜欢玩一个纸杯游戏。

游戏开始前,小 H 在桌上的位置 123 各倒扣一个纸杯,并在其中一个纸杯下面藏了一颗乒乓球。随后小 H 会进行若干次操作,每次把两个位置上的纸杯连同杯下的东西一起对调。

这个游戏的普通玩法是:小 K 先看清乒乓球藏在哪里,等所有对调结束后,猜出球最终的位置。

不过今天她们想玩一种更刺激的新规则:小 K 不知道球的初始位置,但她可以在每一次对调之后都猜一次球所在的位置。

小 H 知道球的真实位置,游戏结束后会告诉小 K 她一共猜对了多少次,作为她的得分。

现在给出全部对调操作和小 K 每次的猜测,但不给出球的初始位置,请你求出小 K 可能获得的最高得分。

输入

第一行包含一个整数 N,表示对调的次数。

接下来 N 行,每行描述一个回合,包含三个整数 abg,表示小 H 对调了位置 ab 上的纸杯,然后小 K 猜球在位置 g

输出

输出小 K 可能获得的最高得分。

样例

输入

2
1 2 2
2 3 3

输出

2

输入

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

输出

2

输入

8
1 2 1
2 3 2
1 3 3
2 1 2
3 2 1
1 3 2
2 3 3
1 2 1

输出

4
说明

样例解释 1

如果球开始时在位置 1:第一次对调后球到位置 2,小 K 猜 2,猜中;第二次对调后球到位置 3,小 K 猜 3,又猜中,共 2 分。

如果球开始时在位置 2 或位置 3,可以验证小 K 一次也猜不中。

因此最高得分为 2

数据规模

对于 100\% 的数据,满足 1 \leq N \leq 100abg 三个数均为 123 之一,且 a \neq b

标签
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 0
通过人数 0
金币数量 2 枚
难度 基础


上一题 下一题