No submission language available for this problem.

Background

小码酱和小码君是好朋友，他们喜欢玩捉迷藏游戏。现在有N个谷仓，小码君开始在第一个谷仓，小码酱为了不被小码君找到，决定躲在距离第一个谷仓最远的谷仓里。为了确定最远的躲藏地点，你需要找到距离第一个谷仓最远的谷仓编号，并计算出这个最远距离以及与第一个谷仓距离最远的谷仓的个数。

Description

给定N个谷仓和M个两两谷仓间的无向边，现在要求找到距离第一个谷仓（小码君那里）最远的谷仓的编号。如果有多个谷仓与第一个谷仓的最远距离相同，则输出编号最小的那个谷仓。同时，需要计算出这个最远距离以及与第一个谷仓距离最远的谷仓的个数，并可能需要输出路径。

Format

Input

输入的第一行包含两个正整数 $N$ 和 $M，K$ ，分别表示谷仓的个数和无向边的个数。以及是否输出路径。$K$ 的取值只有 $0$ 和 $1$

Output

输出一行，包含三个整数，分别表示距离第一个谷仓最远的谷仓的编号、最远距离以及与第一个谷仓距离最远的谷仓的个数。

如果 $K$ 为 $1$ 则额外要输出路径，$0$ 则不需要输出。

Samples

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

4 2 3

5 4 1
1 2
2 3
3 4
2 5

4 3 1
1 2 3 4

Limitation

$n <= 1000, m <= 1000$