#include <bits/stdc++.h>
#include "diameter.h"
using namespace std;

const int N = 100010;
struct Path {int x, y;};
int n, dist[N], val_12[N], val_12_min, pt; bool path[N];
inline Path get_edge()
{
	Path res = {1, 2}; val_12_min = 1e9;
	for(int i = 3; i <= n; ++i)
		val_12[i] = query(1, 2, i), val_12_min = min(val_12_min, val_12[i]);
	if(val_12_min == 4)
	{
		int val_12_min_cnt = 0, pos_q = 0;
		for(int i = 3; i <= n; ++i)
			if(val_12[i] == val_12_min)
				++val_12_min_cnt, pos_q = i;
		if(val_12_min_cnt == 1 && in(pos_q, res.x, res.y))
		{
			path[res.x] = path[res.y] = path[pos_q] = true;
			pt = res.y, dist[pt] = 1; return {res.x, pos_q};
		}
		else {path[res.x] = path[res.y] = true; return res;}
	}
	else
	{
		vector < int > on_path, on_path_val; int on_path_max = -1;
		for(int i = 3; i <= n; ++i)
			if(val_12[i] == val_12_min)
				on_path.push_back(i), path[i] = true;
		path[res.x] = path[res.y] = true;
		if(on_path.size() == 2)
		{
			pt = res.y, dist[res.y] = 2;
			if(in(on_path[0], res.x, on_path[1])) return {res.x, on_path[0]};
			else return {res.x, on_path[1]};
		}
		dist[res.x] = val_12_min / 2 - 1; pt = res.x;
		for(int i = 0; i < (int)on_path.size() - 1; ++i)
		{
			int cur = query(res.x, on_path[i], on_path[i + 1]);
			on_path_val.push_back(cur); on_path_max = max(on_path_max, cur);
		}
		if(on_path_val[0] == on_path_max && on_path_val[1] != on_path_max) return {on_path[0], res.y};
		else if(on_path_val[(int)on_path_val.size() - 1] == on_path_max && on_path_val[(int)on_path_val.size() - 2] != on_path_max) return {on_path.back(), res.y};
		for(int i = 0; i < (int)on_path_val.size() - 1; ++i)
			if(on_path_val[i] == on_path_max && on_path_val[i + 1] == on_path_max)
				return {on_path[i + 1], res.y};
	}
}

pair < int, int > find_diameter(int task_id, int task_n)
{
	n = task_n; pt = 0;
	for(int i = 1; i <= n; ++i) path[i] = false, dist[i] = -1;
	if(n == 1) return {1, 1};
	if(n == 2) return {1, 2};
	Path rt = get_edge();
	for(int i = 1; i <= n; ++i)
	{
		if(path[i] || i == rt.x || i == rt.y) continue;
		dist[i] = query(i, rt.x, rt.y) / 2 - 1;
		if(dist[i] > dist[pt]) pt = i;
	}
	int len = dist[pt] + 1; pair < int, int > res = {0, 0};
	if(in(rt.x, pt, rt.y)) res = {pt, rt.y};
	else res = {pt, rt.x};
	for(int i = 1; i <= n; ++i)
	{
		if(i == pt || dist[i] == -1) continue;
		int cur = query(i, pt, rt.x);
		if(cur == 2 * (dist[i] + dist[pt] + 1))
		{
			if(cur / 2 > len)
			{
				len = cur / 2;
				res = {i, pt};
			}
		}
		else
		{
			if(cur - dist[i] - dist[pt] > len)
			{
				len = cur - dist[i] - dist[pt];
				res = {i, pt};
			}
		}
	}
	return res;
}