“—— 你们如何维持一个用户不为服务付费的商业模式？” “—— 参议员，我们投放广告。” —— 马克·扎克伯格的证词。

许多 IT 公司的大部分利润来自于用户每次进入其网站、应用程序等时售出的广告位。Back Catalog 公司也是如此。在本题中，我们将考虑关于某个特定主题的广告，该主题希望保持匿名。重要的是，有 $n$ 个用户正在寻找关于该主题的页面，并且有 $m$ 个他们感兴趣的网站。此外，我们给出了一个包含 $k$ 个“用户-网站”对的列表，表示该用户有时会访问该网站。除了列表中提到的访问之外，没有其他对网站的访问。

我们考虑的主题不仅非常具体，而且非常罕见，因此只有两家公司想要购买广告。具体来说，他们可以购买在某个特定网站上向某个特定用户展示广告的独家权利。显然，没有公司会购买不存在的“用户-网站”对的权利。此外，如果一个“用户-网站”对未被使用（这两家公司都没有购买它），那么该用户在该网站上将根本看不到任何广告。

互联网的美好旧时光已经过去，如今有大量的广告规则需要遵守。

第一条规则是，对于每个用户，向其展示第一家公司广告的网站数量与向其展示第二家公司广告的网站数量之差（绝对值）不能超过 $1$。

第二条规则是，对于每个网站，向其展示第一家公司广告的用户数量与向其展示第二家公司广告的用户数量之差（绝对值）也不能超过 $1$。

你被欧盟委员会雇用来验证上述规则的公平性。目前还没有任何“用户-网站”对被广告公司收购。你的目标是在遵守所有规则的前提下，找出第一家公司购买的配对数量与第二家公司购买的配对数量之间可能的最大差值。

输入格式

输入的第一行包含三个整数 $n$、$m$ 和 $k$（$1 \le n, m, k \le 100\,000$），分别表示用户数量、网站数量以及用于广告销售的“用户-网站”对数量。

接下来有 $k$ 行。其中的第 $i$ 行包含两个整数 $u_i$ 和 $v_i$（$1 \le u_i \le n$，$1 \le v_i \le m$），表示用户 $u_i$ 访问了网站 $v_i$。输入中不会重复出现相同的配对。

输出格式

在输出的第一行中，输出两个整数 $a$ 和 $b$（$0 \le b \le a \le k$），分别表示在最不公平的情况下（即最大化 $a - b$ 的情况下），第一家公司应该购买的“用户-网站”对数量和第二家公司应该购买的“用户-网站”对数量。

第二行应包含 $a$ 个互不相同的介于 $1$ 到 $k$ 之间的整数，表示第一家公司应该购买的配对的索引（按输入顺序，从 $1$ 开始编号）。

第三行应包含 $b$ 个互不相同的介于 $1$ 到 $k$ 之间的整数，表示第二家公司应该购买的配对的索引。当然，这些整数中的任何一个都不应该出现在定义第一家公司配对的第二行中。

如果其中某个子集为空，只需将相应的行留空。

在第二行和第三行中，允许以任意顺序输出索引。如果有多种可能的答案，你可以输出其中任意一种。

样例

输入样例 1

3 4 4
1 1
2 2
3 3
3 4

输出样例 1

3 0
1 2 3

输入样例 2

3 3 9
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3

输出样例 2

6 3
1 8 9 3 4 5
2 7 6