题目描述

Andrey Sergeevich 是动物园保安。一天早晨，他发现匿名纸条说：有人在夜里交换了两个笼子的标牌。每个标牌上除了动物名字，还有一个唯一编号。保安不懂动物学，只能利用动物园地图和路线信息来恢复这两个标牌。

动物园有 $n$ 个路口和 $m$ 条有向道路。每条道路旁有一个动物笼子及其标牌编号。任意两路口之间最多有一条道路，无自环。每条道路只允许按指定方向通行。

员工推荐了一些主题路线。每条路线给出起点、终点，以及按顺序经过的标牌编号序列。第一条道路从起点出发，每条后续道路从上一条道路终点出发，最后到达路线终点。每条路线不会经过同一个路口两次。每条道路至少被某条路线经过。

由于恰好有两个标牌被交换，请找出可以交换回来的两个标牌编号，使所有主题路线都真实存在。保证存在解。

输入格式

第一行两个整数 $n,m$。

$$1\le n,m\le 100000.$$

接下来 $m$ 行，每行三个整数 $a_i,b_i,c_i$，表示有一条从 $a_i$ 到 $b_i$ 的道路，当前标牌编号为 $c_i$。

$$1\le a_i,b_i\le n,\quad a_i\ne b_i,\quad 1\le c_i\le m.$$

所有标牌编号互不相同。

接下来一行一个整数 $k$，表示主题路线数。

$$1\le k\le 100000.$$

接下来 $2k$ 行描述路线。每条路线两行：

第一行三个整数 $l_i,s_i,t_i$，表示路线长度、起点、终点。

$$1\le l_i\le n,\quad 1\le s_i,t_i\le n,\quad s_i\ne t_i.$$

第二行 $l_i$ 个整数，表示路线上的标牌编号序列。

保证所有路线总长度不超过 $100000$，每条路线不重复经过同一个路口，且每条道路至少在某条路线中出现。

输出格式

输出两个不同整数，表示应交换回来的两个标牌编号。若有多个答案，输出任意一个。

样例

样例输入

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

样例输出

3 5

样例说明

样例中的动物园地图和两条主题路线如下：

交换编号 3 与 5 的标牌后，地图变为：

此时两条路线都能在地图中真实走通。