题目描述

艾迪有 $n$ 张互不相同的卡牌，每一张卡牌有正反两面，正反两面写着不同的数：第 $i$ 张卡牌正面的数为 $a_i$，背面的数为 $b_i$。所有卡牌上的数都是不超过 $m$ 的正整数。

（我们认为两张卡牌 $x,y$ 相同，当且仅当 $\{a_x,b_x\}=\{a_y,b_y\}$。）

艾迪可以对这些卡牌使用若干次魔法：一次魔法形如挑选两张卡牌 $x,y$，如果 $x$ 和 $y$ 上有相同的数，那么艾迪就可以把写着相同的数的两面吸在一起，形成一张新的卡牌。

例如 $\{1,2\}$ 和 $\{3,2\}$ 可以使用魔法变成 $\{1,3\}$；而艾迪无法对 $\{1,2\}$ 和 $\{3,4\}$ 使用魔法。

由于艾迪喜欢玩原神，所以他对魔法掌握得不熟练，因此他需要保证每次使用魔法后剩余的卡牌都互不相同。

薇儿是一个喜欢新鲜感的人，因此如果一个数在所有卡牌中出现了超过一次她就会感到厌烦。艾迪想对这些卡牌使用若干次魔法后送给薇儿，他想知道如何使用魔法才能使薇儿不感到厌烦。

输入格式

• 第一行两个正整数 $n,m$，表示卡牌数量和卡牌上的数的值域。
• 接下来 $n$ 行，每行两个正整数 $a_i,b_i$，表示第 $i$ 张卡牌正面的数为 $a_i$，背面的数为 $b_i$。

输出格式

• 第一行输出一个字符串：如果艾迪无法使薇儿不感到厌烦，则输出 lose，否则输出 win。
• 若输出 win：
  • 第二行输出一个整数 $cnt$，表示使用魔法的次数。
  • 接下来输出 $cnt$ 行，每行三个整数 $a,b,c$，表示艾迪这一次魔法挑选的两张卡牌上的数形成的可重集为 $\{a,a,b,c\}$。

3 3
1 2
3 1
2 3

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

25 10
6 2
4 1
8 3
7 6
6 3
5 3
7 5
8 5
1 2
3 2
1 6
9 3
5 10
9 7
5 9
4 7
4 10
10 3
3 1
8 10
6 8
7 8
10 1
6 9
6 5

lose

win
4
4 3 5
3 5 7
5 6 7
6 3 7

win
21
3 2 8
8 2 10
6 8 9
5 7 10
5 6 9
10 3 7
1 3 4
7 4 8
1 6 10
3 4 6
8 4 5
6 2 9
9 2 3
3 5 7
7 5 9
9 5 8
4 5 6
5 6 8
2 1 3
10 2 4
6 7 10

数据范围与提示

Subtask：

• Subtask 1（10 pts）：$1 \le m \le 5$。
• Subtask 2（20 pts）：$1 \le n,m \le 100$。
• Subtask 3（30 pts）：$1 \le n,m \le 2000$。
• Subtask 4（40 pts）：无特殊限制。

对于 100% 的数据：$1 \le n,m \le 5000$。