QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#690702#4926. Where Is the Root?Mher77717 4ms3836kbC++204.2kb2024-10-31 00:55:152024-10-31 00:55:16

Judging History

你现在查看的是最新测评结果

  • [2024-10-31 00:55:16]
  • 评测
  • 测评结果:17
  • 用时:4ms
  • 内存:3836kb
  • [2024-10-31 00:55:15]
  • 提交

answer

/* -------------------- Includes -------------------- */
#include <iostream>
#include <iomanip>
#include <array>
#include <string>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <list>
#include <iterator>
#include <numeric>
#include <complex>
#include <utility>
#include <random>
#include <fstream>
#pragma warning(disable : 4996)
#pragma warning(disable : 6031)
using namespace std;

/* -------------------- Typedefs -------------------- */

typedef int itn;
typedef long long ll;
typedef unsigned long long ull;
typedef float fl;
typedef double db;
typedef long double ld;

/* -------------------- Usings -------------------- */

using vi = vector<int>;
using vll = vector<ll>;
using mii = map<int, int>;
using mll = map<ll, ll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

/* -------------------- Defines -------------------- */

#define ff first
#define ss second
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define mpr make_pair
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define all(x) (x).begin(), (x).end()

/* -------------------- Constants -------------------- */

const int MAX = int(1e9 + 5);
const ll MAXL = ll(1e18 + 5);
const ll MOD = ll(1e9 + 7);
const ll MOD2 = ll(998244353);

/* -------------------- Functions -------------------- */

void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}

void precision(int x) {
    cout.setf(ios::fixed | ios::showpoint);
    cout.precision(x);
}

ll gcd(ll a, ll b) {
    while (b) {
        a %= b;
        swap(a, b);
    }
    return a;
}

ll lcm(ll a, ll b) {
    return a / gcd(a, b) * b;
}

ll range_sum(ll a, ll b) {
    ll dif = a - 1, cnt = b - a + 1;
    ll ans = ((b - a + 1) * (b - a + 2)) / 2;
    ans += ((b - a + 1) * dif);
    return ans;
}

string dec_to_bin(ll a) {
    string s = "";
    for (ll i = a; i > 0; ) {
        ll k = i % 2;
        i /= 2;
        char c = k + 48;
        s += c;
    }
    if (a == 0) {
        s = "0";
    }
    reverse(all(s));
    return s;
}

ll bin_to_dec(string s) {
    ll num = 0;
    for (int i = 0; i < s.size(); i++) {
        num *= 2ll;
        num += (s[i] - '0');
    }
    return num;
}

int isPrime(ll a) {
    if (a == 1) return 0;
    for (ll i = 2; i * i <= a; i++) {
        if (a % i == 0) return 0;
    }
    return 1;
}

ll binpow(ll a, ll b) {
    if (!a) return 0;
    ll ans = 1;
    while (b) {
        if (b & 1) {
            ans *= a;
        }
        b >>= 1;
        a *= a;
    }
    return ans;
}

ll binpow_by_mod(ll a, ll b, ll mod) {
    if (!a) return 0;
    ll ans = 1;
    while (b) {
        if (b & 1) {
            ans *= a;
            ans %= mod;
        }
        b >>= 1;
        a *= a;
        a %= mod;
    }
    return ans;
}

/* -------------------- Solution -------------------- */

const int N = 1005;
int cnt[N];
vi g[N];

void slv() {
    int n;
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int x, y;
        cin >> x >> y;
        g[x].pub(y);
        g[y].pub(x);
    }
    int ans = 0, sz = MAX;
    for (int i = 1; i <= n; i++) {
        string resp;
        for (int j = i + 1; j <= n; j++) {
            cout << "? 2 " << i << " " << j << endl;
            cin >> resp;
            if (resp == "YES") {
                cnt[i]++;
                cnt[j]++;
                if (cnt[i] == n - 1 && g[i].size() < sz) {
                    sz = g[i].size();
                    ans = i;
                }
                if (cnt[j] == n - 1 && g[j].size() < sz) {
                    sz = g[j].size();
                    ans = j;
                }
            }
        }
    }
    cout << "! " << ans << endl;
}

void cs() {
    int tstc = 1;
    //cin >> tstc;
    while (tstc--) {
        slv();
    }
}

void precalc() {
    return;
}

int main() {
    fastio();
    precalc();
    precision(0);
    cs();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 7
Accepted

Test #1:

score: 7
Accepted
time: 0ms
memory: 3552kb

input:

7
4 1
1 2
4 3
3 5
3 6
4 7
YES
NO
YES
NO
NO
NO
NO
YES
NO
NO
NO
YES
YES
YES
NO
YES
YES
YES
NO
NO
NO

output:

? 2 1 2
? 2 1 3
? 2 1 4
? 2 1 5
? 2 1 6
? 2 1 7
? 2 2 3
? 2 2 4
? 2 2 5
? 2 2 6
? 2 2 7
? 2 3 4
? 2 3 5
? 2 3 6
? 2 3 7
? 2 4 5
? 2 4 6
? 2 4 7
? 2 5 6
? 2 5 7
? 2 6 7
! 4

result:

ok OK

Test #2:

score: 7
Accepted
time: 1ms
memory: 3624kb

input:

9
5 9
8 6
2 8
1 8
3 6
6 7
1 4
4 5
YES
NO
YES
YES
NO
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
NO
YES
NO
YES
NO
YES
NO
NO
YES
YES
NO
NO
YES
YES
YES
YES
NO
YES
NO
YES

output:

? 2 1 2
? 2 1 3
? 2 1 4
? 2 1 5
? 2 1 6
? 2 1 7
? 2 1 8
? 2 1 9
? 2 2 3
? 2 2 4
? 2 2 5
? 2 2 6
? 2 2 7
? 2 2 8
? 2 2 9
? 2 3 4
? 2 3 5
? 2 3 6
? 2 3 7
? 2 3 8
? 2 3 9
? 2 4 5
? 2 4 6
? 2 4 7
? 2 4 8
? 2 4 9
? 2 5 6
? 2 5 7
? 2 5 8
? 2 5 9
? 2 6 7
? 2 6 8
? 2 6 9
? 2 7 8
? 2 7 9
? 2 8 9
! 2

result:

ok OK

Test #3:

score: 7
Accepted
time: 1ms
memory: 3600kb

input:

9
6 8
2 5
5 1
4 3
5 9
6 3
6 1
7 5
YES
NO
NO
YES
YES
YES
YES
YES
NO
NO
YES
YES
NO
YES
NO
YES
NO
YES
NO
YES
NO
NO
YES
NO
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES

output:

? 2 1 2
? 2 1 3
? 2 1 4
? 2 1 5
? 2 1 6
? 2 1 7
? 2 1 8
? 2 1 9
? 2 2 3
? 2 2 4
? 2 2 5
? 2 2 6
? 2 2 7
? 2 2 8
? 2 2 9
? 2 3 4
? 2 3 5
? 2 3 6
? 2 3 7
? 2 3 8
? 2 3 9
? 2 4 5
? 2 4 6
? 2 4 7
? 2 4 8
? 2 4 9
? 2 5 6
? 2 5 7
? 2 5 8
? 2 5 9
? 2 6 7
? 2 6 8
? 2 6 9
? 2 7 8
? 2 7 9
? 2 8 9
! 8

result:

ok OK

Test #4:

score: 7
Accepted
time: 1ms
memory: 3548kb

input:

9
1 8
9 4
7 8
5 7
3 9
2 5
9 1
4 6
YES
NO
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
NO
YES
NO
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES

output:

? 2 1 2
? 2 1 3
? 2 1 4
? 2 1 5
? 2 1 6
? 2 1 7
? 2 1 8
? 2 1 9
? 2 2 3
? 2 2 4
? 2 2 5
? 2 2 6
? 2 2 7
? 2 2 8
? 2 2 9
? 2 3 4
? 2 3 5
? 2 3 6
? 2 3 7
? 2 3 8
? 2 3 9
? 2 4 5
? 2 4 6
? 2 4 7
? 2 4 8
? 2 4 9
? 2 5 6
? 2 5 7
? 2 5 8
? 2 5 9
? 2 6 7
? 2 6 8
? 2 6 9
? 2 7 8
? 2 7 9
? 2 8 9
! 6

result:

ok OK

Test #5:

score: 7
Accepted
time: 1ms
memory: 3552kb

input:

9
7 1
8 4
2 8
5 2
2 3
1 2
1 9
9 6
YES
YES
NO
NO
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO

output:

? 2 1 2
? 2 1 3
? 2 1 4
? 2 1 5
? 2 1 6
? 2 1 7
? 2 1 8
? 2 1 9
? 2 2 3
? 2 2 4
? 2 2 5
? 2 2 6
? 2 2 7
? 2 2 8
? 2 2 9
? 2 3 4
? 2 3 5
? 2 3 6
? 2 3 7
? 2 3 8
? 2 3 9
? 2 4 5
? 2 4 6
? 2 4 7
? 2 4 8
? 2 4 9
? 2 5 6
? 2 5 7
? 2 5 8
? 2 5 9
? 2 6 7
? 2 6 8
? 2 6 9
? 2 7 8
? 2 7 9
? 2 8 9
! 3

result:

ok OK

Test #6:

score: 7
Accepted
time: 1ms
memory: 3540kb

input:

9
1 5
9 8
3 9
7 9
9 1
6 9
4 6
2 3
NO
NO
NO
YES
NO
NO
NO
YES
YES
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
YES
NO
YES
NO
NO
YES
NO
NO
NO
YES
NO
NO
YES
NO
YES
YES

output:

? 2 1 2
? 2 1 3
? 2 1 4
? 2 1 5
? 2 1 6
? 2 1 7
? 2 1 8
? 2 1 9
? 2 2 3
? 2 2 4
? 2 2 5
? 2 2 6
? 2 2 7
? 2 2 8
? 2 2 9
? 2 3 4
? 2 3 5
? 2 3 6
? 2 3 7
? 2 3 8
? 2 3 9
? 2 4 5
? 2 4 6
? 2 4 7
? 2 4 8
? 2 4 9
? 2 5 6
? 2 5 7
? 2 5 8
? 2 5 9
? 2 6 7
? 2 6 8
? 2 6 9
? 2 7 8
? 2 7 9
? 2 8 9
! 9

result:

ok OK

Test #7:

score: 7
Accepted
time: 1ms
memory: 3788kb

input:

9
5 2
6 3
1 9
2 6
7 4
6 8
7 5
4 9
NO
NO
YES
YES
NO
YES
NO
YES
YES
NO
YES
YES
NO
YES
NO
NO
YES
YES
NO
NO
NO
YES
NO
YES
NO
YES
YES
YES
YES
YES
NO
YES
NO
NO
YES
NO

output:

? 2 1 2
? 2 1 3
? 2 1 4
? 2 1 5
? 2 1 6
? 2 1 7
? 2 1 8
? 2 1 9
? 2 2 3
? 2 2 4
? 2 2 5
? 2 2 6
? 2 2 7
? 2 2 8
? 2 2 9
? 2 3 4
? 2 3 5
? 2 3 6
? 2 3 7
? 2 3 8
? 2 3 9
? 2 4 5
? 2 4 6
? 2 4 7
? 2 4 8
? 2 4 9
? 2 5 6
? 2 5 7
? 2 5 8
? 2 5 9
? 2 6 7
? 2 6 8
? 2 6 9
? 2 7 8
? 2 7 9
? 2 8 9
! 5

result:

ok OK

Test #8:

score: 7
Accepted
time: 0ms
memory: 3832kb

input:

9
7 9
7 8
4 2
5 6
9 1
2 8
3 5
4 5
NO
NO
NO
NO
NO
YES
NO
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
NO
YES
YES
NO
YES
YES
YES
YES
NO
YES
YES
YES
NO
YES
YES
NO
YES
YES
NO

output:

? 2 1 2
? 2 1 3
? 2 1 4
? 2 1 5
? 2 1 6
? 2 1 7
? 2 1 8
? 2 1 9
? 2 2 3
? 2 2 4
? 2 2 5
? 2 2 6
? 2 2 7
? 2 2 8
? 2 2 9
? 2 3 4
? 2 3 5
? 2 3 6
? 2 3 7
? 2 3 8
? 2 3 9
? 2 4 5
? 2 4 6
? 2 4 7
? 2 4 8
? 2 4 9
? 2 5 6
? 2 5 7
? 2 5 8
? 2 5 9
? 2 6 7
? 2 6 8
? 2 6 9
? 2 7 8
? 2 7 9
? 2 8 9
! 7

result:

ok OK

Test #9:

score: 7
Accepted
time: 1ms
memory: 3600kb

input:

9
3 2
8 9
8 5
5 2
4 6
9 1
6 7
3 6
NO
NO
NO
NO
NO
NO
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES

output:

? 2 1 2
? 2 1 3
? 2 1 4
? 2 1 5
? 2 1 6
? 2 1 7
? 2 1 8
? 2 1 9
? 2 2 3
? 2 2 4
? 2 2 5
? 2 2 6
? 2 2 7
? 2 2 8
? 2 2 9
? 2 3 4
? 2 3 5
? 2 3 6
? 2 3 7
? 2 3 8
? 2 3 9
? 2 4 5
? 2 4 6
? 2 4 7
? 2 4 8
? 2 4 9
? 2 5 6
? 2 5 7
? 2 5 8
? 2 5 9
? 2 6 7
? 2 6 8
? 2 6 9
? 2 7 8
? 2 7 9
? 2 8 9
! 9

result:

ok OK

Test #10:

score: 7
Accepted
time: 1ms
memory: 3756kb

input:

9
5 6
3 9
5 9
3 4
2 4
7 6
4 8
7 1
NO
YES
NO
YES
YES
YES
NO
YES
YES
YES
NO
NO
NO
NO
NO
YES
YES
YES
YES
YES
YES
NO
NO
NO
YES
NO
YES
YES
NO
YES
YES
NO
YES
NO
YES
NO

output:

? 2 1 2
? 2 1 3
? 2 1 4
? 2 1 5
? 2 1 6
? 2 1 7
? 2 1 8
? 2 1 9
? 2 2 3
? 2 2 4
? 2 2 5
? 2 2 6
? 2 2 7
? 2 2 8
? 2 2 9
? 2 3 4
? 2 3 5
? 2 3 6
? 2 3 7
? 2 3 8
? 2 3 9
? 2 4 5
? 2 4 6
? 2 4 7
? 2 4 8
? 2 4 9
? 2 5 6
? 2 5 7
? 2 5 8
? 2 5 9
? 2 6 7
? 2 6 8
? 2 6 9
? 2 7 8
? 2 7 9
? 2 8 9
! 3

result:

ok OK

Test #11:

score: 7
Accepted
time: 1ms
memory: 3776kb

input:

9
8 3
7 9
4 3
9 4
5 2
9 6
2 1
8 5
YES
YES
NO
YES
NO
NO
YES
NO
YES
NO
YES
NO
NO
YES
NO
YES
YES
YES
YES
YES
YES
NO
YES
YES
NO
YES
NO
NO
YES
NO
NO
NO
YES
NO
YES
NO

output:

? 2 1 2
? 2 1 3
? 2 1 4
? 2 1 5
? 2 1 6
? 2 1 7
? 2 1 8
? 2 1 9
? 2 2 3
? 2 2 4
? 2 2 5
? 2 2 6
? 2 2 7
? 2 2 8
? 2 2 9
? 2 3 4
? 2 3 5
? 2 3 6
? 2 3 7
? 2 3 8
? 2 3 9
? 2 4 5
? 2 4 6
? 2 4 7
? 2 4 8
? 2 4 9
? 2 5 6
? 2 5 7
? 2 5 8
? 2 5 9
? 2 6 7
? 2 6 8
? 2 6 9
? 2 7 8
? 2 7 9
? 2 8 9
! 3

result:

ok OK

Test #12:

score: 7
Accepted
time: 1ms
memory: 3756kb

input:

9
8 1
1 5
7 1
1 3
1 4
6 1
1 9
2 1
YES
YES
YES
YES
YES
YES
YES
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO

output:

? 2 1 2
? 2 1 3
? 2 1 4
? 2 1 5
? 2 1 6
? 2 1 7
? 2 1 8
? 2 1 9
? 2 2 3
? 2 2 4
? 2 2 5
? 2 2 6
? 2 2 7
? 2 2 8
? 2 2 9
? 2 3 4
? 2 3 5
? 2 3 6
? 2 3 7
? 2 3 8
? 2 3 9
? 2 4 5
? 2 4 6
? 2 4 7
? 2 4 8
? 2 4 9
? 2 5 6
? 2 5 7
? 2 5 8
? 2 5 9
? 2 6 7
? 2 6 8
? 2 6 9
? 2 7 8
? 2 7 9
? 2 8 9
! 1

result:

ok OK

Test #13:

score: 7
Accepted
time: 1ms
memory: 3616kb

input:

9
8 1
2 1
9 1
1 3
1 4
1 7
6 1
5 1
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
YES
YES
YES
YES
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO

output:

? 2 1 2
? 2 1 3
? 2 1 4
? 2 1 5
? 2 1 6
? 2 1 7
? 2 1 8
? 2 1 9
? 2 2 3
? 2 2 4
? 2 2 5
? 2 2 6
? 2 2 7
? 2 2 8
? 2 2 9
? 2 3 4
? 2 3 5
? 2 3 6
? 2 3 7
? 2 3 8
? 2 3 9
? 2 4 5
? 2 4 6
? 2 4 7
? 2 4 8
? 2 4 9
? 2 5 6
? 2 5 7
? 2 5 8
? 2 5 9
? 2 6 7
? 2 6 8
? 2 6 9
? 2 7 8
? 2 7 9
? 2 8 9
! 4

result:

ok OK

Test #14:

score: 7
Accepted
time: 1ms
memory: 3600kb

input:

9
6 1
1 3
1 9
2 1
1 8
1 4
7 1
5 1
YES
YES
YES
YES
YES
YES
YES
YES
NO
NO
NO
YES
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
YES
NO
NO
NO
YES
NO
NO
NO
YES
YES
YES
NO
NO
NO

output:

? 2 1 2
? 2 1 3
? 2 1 4
? 2 1 5
? 2 1 6
? 2 1 7
? 2 1 8
? 2 1 9
? 2 2 3
? 2 2 4
? 2 2 5
? 2 2 6
? 2 2 7
? 2 2 8
? 2 2 9
? 2 3 4
? 2 3 5
? 2 3 6
? 2 3 7
? 2 3 8
? 2 3 9
? 2 4 5
? 2 4 6
? 2 4 7
? 2 4 8
? 2 4 9
? 2 5 6
? 2 5 7
? 2 5 8
? 2 5 9
? 2 6 7
? 2 6 8
? 2 6 9
? 2 7 8
? 2 7 9
? 2 8 9
! 6

result:

ok OK

Test #15:

score: 7
Accepted
time: 1ms
memory: 3828kb

input:

9
4 1
1 6
3 1
1 9
2 1
1 7
1 8
1 5
YES
YES
YES
YES
YES
YES
YES
YES
NO
NO
YES
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
YES
NO
NO
NO
NO
YES
YES
YES
YES
NO
NO
NO
NO
NO
NO

output:

? 2 1 2
? 2 1 3
? 2 1 4
? 2 1 5
? 2 1 6
? 2 1 7
? 2 1 8
? 2 1 9
? 2 2 3
? 2 2 4
? 2 2 5
? 2 2 6
? 2 2 7
? 2 2 8
? 2 2 9
? 2 3 4
? 2 3 5
? 2 3 6
? 2 3 7
? 2 3 8
? 2 3 9
? 2 4 5
? 2 4 6
? 2 4 7
? 2 4 8
? 2 4 9
? 2 5 6
? 2 5 7
? 2 5 8
? 2 5 9
? 2 6 7
? 2 6 8
? 2 6 9
? 2 7 8
? 2 7 9
? 2 8 9
! 5

result:

ok OK

Test #16:

score: 7
Accepted
time: 0ms
memory: 3484kb

input:

9
8 1
1 7
1 9
6 1
3 1
4 1
1 2
5 1
YES
YES
YES
YES
YES
YES
YES
YES
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
YES
NO
NO
NO
YES
NO
NO
YES
NO
NO
YES
YES
NO

output:

? 2 1 2
? 2 1 3
? 2 1 4
? 2 1 5
? 2 1 6
? 2 1 7
? 2 1 8
? 2 1 9
? 2 2 3
? 2 2 4
? 2 2 5
? 2 2 6
? 2 2 7
? 2 2 8
? 2 2 9
? 2 3 4
? 2 3 5
? 2 3 6
? 2 3 7
? 2 3 8
? 2 3 9
? 2 4 5
? 2 4 6
? 2 4 7
? 2 4 8
? 2 4 9
? 2 5 6
? 2 5 7
? 2 5 8
? 2 5 9
? 2 6 7
? 2 6 8
? 2 6 9
? 2 7 8
? 2 7 9
? 2 8 9
! 7

result:

ok OK

Test #17:

score: 7
Accepted
time: 1ms
memory: 3624kb

input:

9
3 5
8 2
8 7
6 1
8 3
9 2
5 1
6 4
NO
YES
YES
YES
YES
YES
YES
NO
NO
NO
NO
NO
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
NO
YES
YES
YES
NO
YES
YES
NO
YES
YES
YES

output:

? 2 1 2
? 2 1 3
? 2 1 4
? 2 1 5
? 2 1 6
? 2 1 7
? 2 1 8
? 2 1 9
? 2 2 3
? 2 2 4
? 2 2 5
? 2 2 6
? 2 2 7
? 2 2 8
? 2 2 9
? 2 3 4
? 2 3 5
? 2 3 6
? 2 3 7
? 2 3 8
? 2 3 9
? 2 4 5
? 2 4 6
? 2 4 7
? 2 4 8
? 2 4 9
? 2 5 6
? 2 5 7
? 2 5 8
? 2 5 9
? 2 6 7
? 2 6 8
? 2 6 9
? 2 7 8
? 2 7 9
? 2 8 9
! 7

result:

ok OK

Test #18:

score: 7
Accepted
time: 1ms
memory: 3488kb

input:

9
2 5
5 4
9 2
6 3
3 9
7 4
1 9
6 8
NO
YES
NO
NO
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES

output:

? 2 1 2
? 2 1 3
? 2 1 4
? 2 1 5
? 2 1 6
? 2 1 7
? 2 1 8
? 2 1 9
? 2 2 3
? 2 2 4
? 2 2 5
? 2 2 6
? 2 2 7
? 2 2 8
? 2 2 9
? 2 3 4
? 2 3 5
? 2 3 6
? 2 3 7
? 2 3 8
? 2 3 9
? 2 4 5
? 2 4 6
? 2 4 7
? 2 4 8
? 2 4 9
? 2 5 6
? 2 5 7
? 2 5 8
? 2 5 9
? 2 6 7
? 2 6 8
? 2 6 9
? 2 7 8
? 2 7 9
? 2 8 9
! 8

result:

ok OK

Test #19:

score: 7
Accepted
time: 0ms
memory: 3792kb

input:

9
7 9
7 5
8 4
1 7
6 2
4 2
9 6
3 5
YES
NO
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES

output:

? 2 1 2
? 2 1 3
? 2 1 4
? 2 1 5
? 2 1 6
? 2 1 7
? 2 1 8
? 2 1 9
? 2 2 3
? 2 2 4
? 2 2 5
? 2 2 6
? 2 2 7
? 2 2 8
? 2 2 9
? 2 3 4
? 2 3 5
? 2 3 6
? 2 3 7
? 2 3 8
? 2 3 9
? 2 4 5
? 2 4 6
? 2 4 7
? 2 4 8
? 2 4 9
? 2 5 6
? 2 5 7
? 2 5 8
? 2 5 9
? 2 6 7
? 2 6 8
? 2 6 9
? 2 7 8
? 2 7 9
? 2 8 9
! 8

result:

ok OK

Test #20:

score: 7
Accepted
time: 1ms
memory: 3568kb

input:

9
9 7
1 8
2 7
4 5
1 9
6 8
5 2
8 3
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
NO
YES
YES
YES
NO
YES
NO
YES
YES
YES

output:

? 2 1 2
? 2 1 3
? 2 1 4
? 2 1 5
? 2 1 6
? 2 1 7
? 2 1 8
? 2 1 9
? 2 2 3
? 2 2 4
? 2 2 5
? 2 2 6
? 2 2 7
? 2 2 8
? 2 2 9
? 2 3 4
? 2 3 5
? 2 3 6
? 2 3 7
? 2 3 8
? 2 3 9
? 2 4 5
? 2 4 6
? 2 4 7
? 2 4 8
? 2 4 9
? 2 5 6
? 2 5 7
? 2 5 8
? 2 5 9
? 2 6 7
? 2 6 8
? 2 6 9
? 2 7 8
? 2 7 9
? 2 8 9
! 3

result:

ok OK

Test #21:

score: 7
Accepted
time: 1ms
memory: 3628kb

input:

9
4 9
7 5
1 7
1 3
5 8
1 9
6 4
2 6
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
NO
NO
YES
YES
YES
YES
YES
YES
YES
NO
YES
NO
NO
YES
NO
YES
YES
NO
NO
NO
YES
YES
NO
NO

output:

? 2 1 2
? 2 1 3
? 2 1 4
? 2 1 5
? 2 1 6
? 2 1 7
? 2 1 8
? 2 1 9
? 2 2 3
? 2 2 4
? 2 2 5
? 2 2 6
? 2 2 7
? 2 2 8
? 2 2 9
? 2 3 4
? 2 3 5
? 2 3 6
? 2 3 7
? 2 3 8
? 2 3 9
? 2 4 5
? 2 4 6
? 2 4 7
? 2 4 8
? 2 4 9
? 2 5 6
? 2 5 7
? 2 5 8
? 2 5 9
? 2 6 7
? 2 6 8
? 2 6 9
? 2 7 8
? 2 7 9
? 2 8 9
! 3

result:

ok OK

Test #22:

score: 7
Accepted
time: 0ms
memory: 3548kb

input:

9
5 3
6 4
5 2
4 9
7 2
9 7
1 3
8 3
NO
YES
NO
NO
NO
NO
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES

output:

? 2 1 2
? 2 1 3
? 2 1 4
? 2 1 5
? 2 1 6
? 2 1 7
? 2 1 8
? 2 1 9
? 2 2 3
? 2 2 4
? 2 2 5
? 2 2 6
? 2 2 7
? 2 2 8
? 2 2 9
? 2 3 4
? 2 3 5
? 2 3 6
? 2 3 7
? 2 3 8
? 2 3 9
? 2 4 5
? 2 4 6
? 2 4 7
? 2 4 8
? 2 4 9
? 2 5 6
? 2 5 7
? 2 5 8
? 2 5 9
? 2 6 7
? 2 6 8
? 2 6 9
? 2 7 8
? 2 7 9
? 2 8 9
! 8

result:

ok OK

Test #23:

score: 7
Accepted
time: 1ms
memory: 3756kb

input:

9
8 2
9 3
6 1
8 5
3 4
7 8
4 1
2 6
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
NO
YES

output:

? 2 1 2
? 2 1 3
? 2 1 4
? 2 1 5
? 2 1 6
? 2 1 7
? 2 1 8
? 2 1 9
? 2 2 3
? 2 2 4
? 2 2 5
? 2 2 6
? 2 2 7
? 2 2 8
? 2 2 9
? 2 3 4
? 2 3 5
? 2 3 6
? 2 3 7
? 2 3 8
? 2 3 9
? 2 4 5
? 2 4 6
? 2 4 7
? 2 4 8
? 2 4 9
? 2 5 6
? 2 5 7
? 2 5 8
? 2 5 9
? 2 6 7
? 2 6 8
? 2 6 9
? 2 7 8
? 2 7 9
? 2 8 9
! 5

result:

ok OK

Subtask #2:

score: 10
Accepted

Test #24:

score: 10
Accepted
time: 3ms
memory: 3524kb

input:

30
1 15
29 30
1 4
7 28
29 17
1 26
26 7
12 5
27 13
3 7
27 1
21 15
9 22
22 5
24 27
19 1
25 30
22 27
6 15
16 13
18 2
27 10
27 30
20 26
8 15
18 8
14 1
27 23
11 3
YES
YES
YES
NO
YES
YES
YES
NO
NO
YES
NO
NO
YES
YES
NO
NO
YES
YES
YES
YES
NO
YES
NO
NO
YES
YES
YES
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
Y...

output:

? 2 1 2
? 2 1 3
? 2 1 4
? 2 1 5
? 2 1 6
? 2 1 7
? 2 1 8
? 2 1 9
? 2 1 10
? 2 1 11
? 2 1 12
? 2 1 13
? 2 1 14
? 2 1 15
? 2 1 16
? 2 1 17
? 2 1 18
? 2 1 19
? 2 1 20
? 2 1 21
? 2 1 22
? 2 1 23
? 2 1 24
? 2 1 25
? 2 1 26
? 2 1 27
? 2 1 28
? 2 1 29
? 2 1 30
? 2 2 3
? 2 2 4
? 2 2 5
? 2 2 6
? 2 2 7
? 2 2 8...

result:

ok OK

Test #25:

score: 10
Accepted
time: 3ms
memory: 3488kb

input:

30
15 16
8 6
19 2
26 17
30 15
26 4
1 6
1 23
15 1
29 25
21 3
12 1
2 24
29 22
9 1
3 10
27 28
5 12
20 5
14 7
5 26
7 18
10 23
1 28
3 11
7 1
19 23
13 23
29 30
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
...

output:

? 2 1 2
? 2 1 3
? 2 1 4
? 2 1 5
? 2 1 6
? 2 1 7
? 2 1 8
? 2 1 9
? 2 1 10
? 2 1 11
? 2 1 12
? 2 1 13
? 2 1 14
? 2 1 15
? 2 1 16
? 2 1 17
? 2 1 18
? 2 1 19
? 2 1 20
? 2 1 21
? 2 1 22
? 2 1 23
? 2 1 24
? 2 1 25
? 2 1 26
? 2 1 27
? 2 1 28
? 2 1 29
? 2 1 30
? 2 2 3
? 2 2 4
? 2 2 5
? 2 2 6
? 2 2 7
? 2 2 8...

result:

ok OK

Test #26:

score: 10
Accepted
time: 3ms
memory: 3536kb

input:

30
19 7
14 27
22 18
15 19
1 18
27 23
21 28
19 24
25 10
27 3
23 7
9 26
20 4
7 9
12 19
6 19
23 17
18 5
5 8
21 25
10 30
9 1
5 29
2 7
12 10
11 6
4 10
26 13
5 16
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
NO
YES
NO
NO
YES
NO
YES
NO
YES
NO
NO
N...

output:

? 2 1 2
? 2 1 3
? 2 1 4
? 2 1 5
? 2 1 6
? 2 1 7
? 2 1 8
? 2 1 9
? 2 1 10
? 2 1 11
? 2 1 12
? 2 1 13
? 2 1 14
? 2 1 15
? 2 1 16
? 2 1 17
? 2 1 18
? 2 1 19
? 2 1 20
? 2 1 21
? 2 1 22
? 2 1 23
? 2 1 24
? 2 1 25
? 2 1 26
? 2 1 27
? 2 1 28
? 2 1 29
? 2 1 30
? 2 2 3
? 2 2 4
? 2 2 5
? 2 2 6
? 2 2 7
? 2 2 8...

result:

ok OK

Test #27:

score: 10
Accepted
time: 3ms
memory: 3628kb

input:

30
11 30
5 27
13 8
29 2
17 23
1 15
21 16
3 1
9 20
26 8
9 12
12 29
17 22
1 2
12 16
5 10
19 18
1 14
5 7
18 12
8 1
5 25
29 24
3 28
5 8
12 23
6 4
1 6
11 23
YES
YES
YES
NO
YES
NO
YES
YES
NO
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
NO
YES
YES
YES
NO
NO
NO
NO
NO
YES
YES
NO
YES
YES
NO
N...

output:

? 2 1 2
? 2 1 3
? 2 1 4
? 2 1 5
? 2 1 6
? 2 1 7
? 2 1 8
? 2 1 9
? 2 1 10
? 2 1 11
? 2 1 12
? 2 1 13
? 2 1 14
? 2 1 15
? 2 1 16
? 2 1 17
? 2 1 18
? 2 1 19
? 2 1 20
? 2 1 21
? 2 1 22
? 2 1 23
? 2 1 24
? 2 1 25
? 2 1 26
? 2 1 27
? 2 1 28
? 2 1 29
? 2 1 30
? 2 2 3
? 2 2 4
? 2 2 5
? 2 2 6
? 2 2 7
? 2 2 8...

result:

ok OK

Test #28:

score: 10
Accepted
time: 3ms
memory: 3620kb

input:

30
28 6
22 15
7 26
24 17
16 18
30 19
25 5
16 11
11 13
6 1
24 6
27 24
29 14
17 21
5 20
23 2
12 27
20 29
9 23
15 4
24 29
16 6
10 26
5 30
23 27
9 15
1 7
3 1
8 11
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
NO
NO
YES
NO
NO
NO
NO
...

output:

? 2 1 2
? 2 1 3
? 2 1 4
? 2 1 5
? 2 1 6
? 2 1 7
? 2 1 8
? 2 1 9
? 2 1 10
? 2 1 11
? 2 1 12
? 2 1 13
? 2 1 14
? 2 1 15
? 2 1 16
? 2 1 17
? 2 1 18
? 2 1 19
? 2 1 20
? 2 1 21
? 2 1 22
? 2 1 23
? 2 1 24
? 2 1 25
? 2 1 26
? 2 1 27
? 2 1 28
? 2 1 29
? 2 1 30
? 2 2 3
? 2 2 4
? 2 2 5
? 2 2 6
? 2 2 7
? 2 2 8...

result:

ok OK

Test #29:

score: 10
Accepted
time: 1ms
memory: 3628kb

input:

30
25 21
29 13
16 30
22 27
29 9
6 19
11 20
17 2
5 24
20 7
28 26
17 30
12 23
12 19
12 5
1 27
20 5
29 19
21 23
11 4
26 10
15 5
1 14
28 23
1 11
30 18
1 30
8 21
12 3
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
...

output:

? 2 1 2
? 2 1 3
? 2 1 4
? 2 1 5
? 2 1 6
? 2 1 7
? 2 1 8
? 2 1 9
? 2 1 10
? 2 1 11
? 2 1 12
? 2 1 13
? 2 1 14
? 2 1 15
? 2 1 16
? 2 1 17
? 2 1 18
? 2 1 19
? 2 1 20
? 2 1 21
? 2 1 22
? 2 1 23
? 2 1 24
? 2 1 25
? 2 1 26
? 2 1 27
? 2 1 28
? 2 1 29
? 2 1 30
? 2 2 3
? 2 2 4
? 2 2 5
? 2 2 6
? 2 2 7
? 2 2 8...

result:

ok OK

Test #30:

score: 10
Accepted
time: 2ms
memory: 3832kb

input:

30
11 29
30 15
11 30
23 12
1 21
30 1
18 1
7 23
1 28
6 9
9 24
8 7
30 8
9 26
30 27
16 6
30 5
20 29
14 25
14 28
24 11
26 19
4 22
10 22
3 28
2 7
28 22
1 17
11 13
NO
YES
YES
NO
NO
NO
NO
NO
YES
YES
NO
YES
YES
NO
NO
YES
YES
NO
NO
YES
YES
NO
NO
YES
NO
NO
YES
NO
YES
NO
NO
NO
NO
YES
YES
NO
NO
YES
NO
YES
NO
NO...

output:

? 2 1 2
? 2 1 3
? 2 1 4
? 2 1 5
? 2 1 6
? 2 1 7
? 2 1 8
? 2 1 9
? 2 1 10
? 2 1 11
? 2 1 12
? 2 1 13
? 2 1 14
? 2 1 15
? 2 1 16
? 2 1 17
? 2 1 18
? 2 1 19
? 2 1 20
? 2 1 21
? 2 1 22
? 2 1 23
? 2 1 24
? 2 1 25
? 2 1 26
? 2 1 27
? 2 1 28
? 2 1 29
? 2 1 30
? 2 2 3
? 2 2 4
? 2 2 5
? 2 2 6
? 2 2 7
? 2 2 8...

result:

ok OK

Test #31:

score: 10
Accepted
time: 3ms
memory: 3836kb

input:

30
11 27
27 26
23 13
8 30
14 9
1 5
22 16
1 14
1 10
17 21
26 25
9 28
3 13
14 3
12 30
1 15
26 19
26 1
29 2
7 14
17 4
2 9
20 9
1 30
14 17
20 18
6 14
24 19
8 22
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
NO
YES
YES
YES
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO...

output:

? 2 1 2
? 2 1 3
? 2 1 4
? 2 1 5
? 2 1 6
? 2 1 7
? 2 1 8
? 2 1 9
? 2 1 10
? 2 1 11
? 2 1 12
? 2 1 13
? 2 1 14
? 2 1 15
? 2 1 16
? 2 1 17
? 2 1 18
? 2 1 19
? 2 1 20
? 2 1 21
? 2 1 22
? 2 1 23
? 2 1 24
? 2 1 25
? 2 1 26
? 2 1 27
? 2 1 28
? 2 1 29
? 2 1 30
? 2 2 3
? 2 2 4
? 2 2 5
? 2 2 6
? 2 2 7
? 2 2 8...

result:

ok OK

Test #32:

score: 10
Accepted
time: 3ms
memory: 3488kb

input:

30
8 23
5 11
11 15
26 27
28 5
17 22
17 16
21 20
12 4
12 10
7 3
24 29
30 10
3 12
30 6
21 22
23 1
6 25
9 19
14 2
20 18
2 29
7 9
13 24
15 18
27 16
8 28
19 13
14 26
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
YES
NO
NO
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YE...

output:

? 2 1 2
? 2 1 3
? 2 1 4
? 2 1 5
? 2 1 6
? 2 1 7
? 2 1 8
? 2 1 9
? 2 1 10
? 2 1 11
? 2 1 12
? 2 1 13
? 2 1 14
? 2 1 15
? 2 1 16
? 2 1 17
? 2 1 18
? 2 1 19
? 2 1 20
? 2 1 21
? 2 1 22
? 2 1 23
? 2 1 24
? 2 1 25
? 2 1 26
? 2 1 27
? 2 1 28
? 2 1 29
? 2 1 30
? 2 2 3
? 2 2 4
? 2 2 5
? 2 2 6
? 2 2 7
? 2 2 8...

result:

ok OK

Test #33:

score: 10
Accepted
time: 2ms
memory: 3820kb

input:

30
19 29
28 30
17 21
2 14
3 9
9 16
28 12
12 14
18 11
15 2
26 10
21 16
24 15
23 8
17 25
7 5
24 7
7 13
1 29
25 10
6 4
11 27
20 5
6 30
22 4
19 26
27 23
3 8
18 22
NO
YES
NO
NO
NO
NO
YES
YES
YES
YES
NO
NO
NO
NO
YES
YES
NO
YES
NO
YES
NO
YES
NO
YES
YES
YES
NO
YES
NO
NO
YES
YES
YES
YES
NO
NO
NO
YES
YES
YES
...

output:

? 2 1 2
? 2 1 3
? 2 1 4
? 2 1 5
? 2 1 6
? 2 1 7
? 2 1 8
? 2 1 9
? 2 1 10
? 2 1 11
? 2 1 12
? 2 1 13
? 2 1 14
? 2 1 15
? 2 1 16
? 2 1 17
? 2 1 18
? 2 1 19
? 2 1 20
? 2 1 21
? 2 1 22
? 2 1 23
? 2 1 24
? 2 1 25
? 2 1 26
? 2 1 27
? 2 1 28
? 2 1 29
? 2 1 30
? 2 2 3
? 2 2 4
? 2 2 5
? 2 2 6
? 2 2 7
? 2 2 8...

result:

ok OK

Test #34:

score: 10
Accepted
time: 2ms
memory: 3532kb

input:

30
8 23
26 25
24 21
28 12
19 29
1 19
14 30
16 24
9 23
4 3
6 21
8 18
29 4
11 5
22 27
25 23
10 28
10 16
3 22
30 20
11 15
2 14
18 2
13 7
17 15
13 27
12 20
5 6
7 17
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YE...

output:

? 2 1 2
? 2 1 3
? 2 1 4
? 2 1 5
? 2 1 6
? 2 1 7
? 2 1 8
? 2 1 9
? 2 1 10
? 2 1 11
? 2 1 12
? 2 1 13
? 2 1 14
? 2 1 15
? 2 1 16
? 2 1 17
? 2 1 18
? 2 1 19
? 2 1 20
? 2 1 21
? 2 1 22
? 2 1 23
? 2 1 24
? 2 1 25
? 2 1 26
? 2 1 27
? 2 1 28
? 2 1 29
? 2 1 30
? 2 2 3
? 2 2 4
? 2 2 5
? 2 2 6
? 2 2 7
? 2 2 8...

result:

ok OK

Test #35:

score: 10
Accepted
time: 1ms
memory: 3612kb

input:

30
7 6
29 28
7 22
16 12
5 3
13 10
27 6
2 30
11 30
25 26
27 28
12 23
19 23
19 22
9 29
1 2
21 4
10 18
15 8
20 17
21 9
26 5
18 15
4 24
16 3
8 24
11 25
20 13
20 14
YES
YES
NO
YES
NO
NO
NO
NO
NO
YES
YES
NO
NO
NO
YES
NO
NO
YES
NO
NO
YES
YES
NO
YES
YES
NO
NO
NO
YES
YES
NO
YES
NO
NO
NO
NO
NO
YES
YES
NO
NO
N...

output:

? 2 1 2
? 2 1 3
? 2 1 4
? 2 1 5
? 2 1 6
? 2 1 7
? 2 1 8
? 2 1 9
? 2 1 10
? 2 1 11
? 2 1 12
? 2 1 13
? 2 1 14
? 2 1 15
? 2 1 16
? 2 1 17
? 2 1 18
? 2 1 19
? 2 1 20
? 2 1 21
? 2 1 22
? 2 1 23
? 2 1 24
? 2 1 25
? 2 1 26
? 2 1 27
? 2 1 28
? 2 1 29
? 2 1 30
? 2 2 3
? 2 2 4
? 2 2 5
? 2 2 6
? 2 2 7
? 2 2 8...

result:

ok OK

Test #36:

score: 10
Accepted
time: 3ms
memory: 3560kb

input:

30
9 12
19 8
15 26
23 7
3 20
14 3
27 30
28 17
9 20
18 7
13 6
21 13
5 21
1 8
26 29
2 28
24 2
18 12
22 27
4 15
25 4
24 23
16 3
10 6
22 25
29 11
30 19
10 11
17 5
NO
NO
YES
YES
YES
NO
YES
NO
YES
YES
NO
YES
NO
YES
NO
YES
NO
YES
NO
YES
YES
NO
NO
YES
YES
YES
YES
YES
YES
YES
NO
NO
NO
YES
NO
YES
NO
NO
YES
NO...

output:

? 2 1 2
? 2 1 3
? 2 1 4
? 2 1 5
? 2 1 6
? 2 1 7
? 2 1 8
? 2 1 9
? 2 1 10
? 2 1 11
? 2 1 12
? 2 1 13
? 2 1 14
? 2 1 15
? 2 1 16
? 2 1 17
? 2 1 18
? 2 1 19
? 2 1 20
? 2 1 21
? 2 1 22
? 2 1 23
? 2 1 24
? 2 1 25
? 2 1 26
? 2 1 27
? 2 1 28
? 2 1 29
? 2 1 30
? 2 2 3
? 2 2 4
? 2 2 5
? 2 2 6
? 2 2 7
? 2 2 8...

result:

ok OK

Test #37:

score: 10
Accepted
time: 3ms
memory: 3548kb

input:

30
26 1
1 28
1 5
25 1
29 1
1 19
27 1
1 9
12 1
1 15
11 1
23 1
4 1
18 1
1 20
1 6
1 16
1 21
1 14
30 1
1 7
3 1
1 10
1 13
1 22
24 1
17 1
1 8
1 2
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
N...

output:

? 2 1 2
? 2 1 3
? 2 1 4
? 2 1 5
? 2 1 6
? 2 1 7
? 2 1 8
? 2 1 9
? 2 1 10
? 2 1 11
? 2 1 12
? 2 1 13
? 2 1 14
? 2 1 15
? 2 1 16
? 2 1 17
? 2 1 18
? 2 1 19
? 2 1 20
? 2 1 21
? 2 1 22
? 2 1 23
? 2 1 24
? 2 1 25
? 2 1 26
? 2 1 27
? 2 1 28
? 2 1 29
? 2 1 30
? 2 2 3
? 2 2 4
? 2 2 5
? 2 2 6
? 2 2 7
? 2 2 8...

result:

ok OK

Test #38:

score: 10
Accepted
time: 0ms
memory: 3600kb

input:

30
1 27
1 5
1 11
14 1
2 1
13 1
25 1
8 1
6 1
15 1
7 1
29 1
3 1
28 1
1 26
1 10
1 12
18 1
1 19
1 23
1 4
30 1
22 1
9 1
20 1
1 24
16 1
17 1
1 21
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
N...

output:

? 2 1 2
? 2 1 3
? 2 1 4
? 2 1 5
? 2 1 6
? 2 1 7
? 2 1 8
? 2 1 9
? 2 1 10
? 2 1 11
? 2 1 12
? 2 1 13
? 2 1 14
? 2 1 15
? 2 1 16
? 2 1 17
? 2 1 18
? 2 1 19
? 2 1 20
? 2 1 21
? 2 1 22
? 2 1 23
? 2 1 24
? 2 1 25
? 2 1 26
? 2 1 27
? 2 1 28
? 2 1 29
? 2 1 30
? 2 2 3
? 2 2 4
? 2 2 5
? 2 2 6
? 2 2 7
? 2 2 8...

result:

ok OK

Test #39:

score: 10
Accepted
time: 0ms
memory: 3752kb

input:

30
5 1
1 13
26 1
9 1
1 24
1 15
16 1
1 27
22 1
1 10
1 8
17 1
1 7
1 21
1 3
2 1
4 1
14 1
25 1
6 1
20 1
1 18
1 30
11 1
1 19
1 12
1 28
29 1
1 23
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO...

output:

? 2 1 2
? 2 1 3
? 2 1 4
? 2 1 5
? 2 1 6
? 2 1 7
? 2 1 8
? 2 1 9
? 2 1 10
? 2 1 11
? 2 1 12
? 2 1 13
? 2 1 14
? 2 1 15
? 2 1 16
? 2 1 17
? 2 1 18
? 2 1 19
? 2 1 20
? 2 1 21
? 2 1 22
? 2 1 23
? 2 1 24
? 2 1 25
? 2 1 26
? 2 1 27
? 2 1 28
? 2 1 29
? 2 1 30
? 2 2 3
? 2 2 4
? 2 2 5
? 2 2 6
? 2 2 7
? 2 2 8...

result:

ok OK

Test #40:

score: 10
Accepted
time: 3ms
memory: 3540kb

input:

30
5 1
1 27
15 1
1 17
29 1
22 1
1 6
1 2
1 18
1 19
10 1
26 1
3 1
11 1
1 24
1 23
4 1
1 16
1 30
7 1
12 1
14 1
8 1
21 1
1 28
25 1
20 1
1 13
9 1
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
N...

output:

? 2 1 2
? 2 1 3
? 2 1 4
? 2 1 5
? 2 1 6
? 2 1 7
? 2 1 8
? 2 1 9
? 2 1 10
? 2 1 11
? 2 1 12
? 2 1 13
? 2 1 14
? 2 1 15
? 2 1 16
? 2 1 17
? 2 1 18
? 2 1 19
? 2 1 20
? 2 1 21
? 2 1 22
? 2 1 23
? 2 1 24
? 2 1 25
? 2 1 26
? 2 1 27
? 2 1 28
? 2 1 29
? 2 1 30
? 2 2 3
? 2 2 4
? 2 2 5
? 2 2 6
? 2 2 7
? 2 2 8...

result:

ok OK

Test #41:

score: 10
Accepted
time: 0ms
memory: 3556kb

input:

30
1 23
8 1
30 1
5 1
15 1
6 1
1 9
1 27
1 11
1 26
1 16
1 24
1 12
1 4
1 18
1 20
1 17
1 28
1 22
21 1
29 1
1 14
13 1
2 1
1 7
25 1
10 1
3 1
1 19
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
...

output:

? 2 1 2
? 2 1 3
? 2 1 4
? 2 1 5
? 2 1 6
? 2 1 7
? 2 1 8
? 2 1 9
? 2 1 10
? 2 1 11
? 2 1 12
? 2 1 13
? 2 1 14
? 2 1 15
? 2 1 16
? 2 1 17
? 2 1 18
? 2 1 19
? 2 1 20
? 2 1 21
? 2 1 22
? 2 1 23
? 2 1 24
? 2 1 25
? 2 1 26
? 2 1 27
? 2 1 28
? 2 1 29
? 2 1 30
? 2 2 3
? 2 2 4
? 2 2 5
? 2 2 6
? 2 2 7
? 2 2 8...

result:

ok OK

Test #42:

score: 10
Accepted
time: 0ms
memory: 3528kb

input:

30
28 1
1 17
1 2
21 1
16 1
20 1
29 1
1 19
24 1
5 1
1 13
1 15
1 12
7 1
9 1
1 26
1 25
1 3
6 1
1 30
1 8
4 1
1 14
11 1
27 1
1 10
18 1
22 1
1 23
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO...

output:

? 2 1 2
? 2 1 3
? 2 1 4
? 2 1 5
? 2 1 6
? 2 1 7
? 2 1 8
? 2 1 9
? 2 1 10
? 2 1 11
? 2 1 12
? 2 1 13
? 2 1 14
? 2 1 15
? 2 1 16
? 2 1 17
? 2 1 18
? 2 1 19
? 2 1 20
? 2 1 21
? 2 1 22
? 2 1 23
? 2 1 24
? 2 1 25
? 2 1 26
? 2 1 27
? 2 1 28
? 2 1 29
? 2 1 30
? 2 2 3
? 2 2 4
? 2 2 5
? 2 2 6
? 2 2 7
? 2 2 8...

result:

ok OK

Test #43:

score: 10
Accepted
time: 3ms
memory: 3532kb

input:

30
8 1
21 1
1 5
26 1
1 28
1 30
24 1
7 1
6 1
11 1
18 1
25 1
10 1
4 1
1 19
15 1
1 9
1 14
1 3
1 29
16 1
1 13
1 20
1 27
1 12
1 17
2 1
1 22
1 23
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
...

output:

? 2 1 2
? 2 1 3
? 2 1 4
? 2 1 5
? 2 1 6
? 2 1 7
? 2 1 8
? 2 1 9
? 2 1 10
? 2 1 11
? 2 1 12
? 2 1 13
? 2 1 14
? 2 1 15
? 2 1 16
? 2 1 17
? 2 1 18
? 2 1 19
? 2 1 20
? 2 1 21
? 2 1 22
? 2 1 23
? 2 1 24
? 2 1 25
? 2 1 26
? 2 1 27
? 2 1 28
? 2 1 29
? 2 1 30
? 2 2 3
? 2 2 4
? 2 2 5
? 2 2 6
? 2 2 7
? 2 2 8...

result:

ok OK

Test #44:

score: 10
Accepted
time: 3ms
memory: 3588kb

input:

30
10 1
1 24
1 14
1 5
1 19
25 1
17 1
1 3
7 1
1 21
4 1
30 1
29 1
1 6
1 16
27 1
9 1
1 28
11 1
1 18
2 1
22 1
1 15
8 1
1 23
1 26
13 1
1 20
12 1
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO...

output:

? 2 1 2
? 2 1 3
? 2 1 4
? 2 1 5
? 2 1 6
? 2 1 7
? 2 1 8
? 2 1 9
? 2 1 10
? 2 1 11
? 2 1 12
? 2 1 13
? 2 1 14
? 2 1 15
? 2 1 16
? 2 1 17
? 2 1 18
? 2 1 19
? 2 1 20
? 2 1 21
? 2 1 22
? 2 1 23
? 2 1 24
? 2 1 25
? 2 1 26
? 2 1 27
? 2 1 28
? 2 1 29
? 2 1 30
? 2 2 3
? 2 2 4
? 2 2 5
? 2 2 6
? 2 2 7
? 2 2 8...

result:

ok OK

Test #45:

score: 10
Accepted
time: 3ms
memory: 3616kb

input:

30
1 25
14 1
1 8
1 7
27 1
1 4
1 29
1 2
9 1
24 1
5 1
1 28
1 30
1 17
22 1
26 1
16 1
1 13
1 10
19 1
11 1
1 20
1 18
23 1
1 21
15 1
1 12
6 1
1 3
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
N...

output:

? 2 1 2
? 2 1 3
? 2 1 4
? 2 1 5
? 2 1 6
? 2 1 7
? 2 1 8
? 2 1 9
? 2 1 10
? 2 1 11
? 2 1 12
? 2 1 13
? 2 1 14
? 2 1 15
? 2 1 16
? 2 1 17
? 2 1 18
? 2 1 19
? 2 1 20
? 2 1 21
? 2 1 22
? 2 1 23
? 2 1 24
? 2 1 25
? 2 1 26
? 2 1 27
? 2 1 28
? 2 1 29
? 2 1 30
? 2 2 3
? 2 2 4
? 2 2 5
? 2 2 6
? 2 2 7
? 2 2 8...

result:

ok OK

Test #46:

score: 10
Accepted
time: 3ms
memory: 3616kb

input:

30
6 1
29 1
1 18
1 12
14 1
1 30
1 17
26 1
1 20
3 1
1 15
25 1
23 1
1 4
27 1
1 8
1 24
1 10
11 1
1 9
22 1
7 1
13 1
16 1
19 1
28 1
1 2
5 1
21 1
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO...

output:

? 2 1 2
? 2 1 3
? 2 1 4
? 2 1 5
? 2 1 6
? 2 1 7
? 2 1 8
? 2 1 9
? 2 1 10
? 2 1 11
? 2 1 12
? 2 1 13
? 2 1 14
? 2 1 15
? 2 1 16
? 2 1 17
? 2 1 18
? 2 1 19
? 2 1 20
? 2 1 21
? 2 1 22
? 2 1 23
? 2 1 24
? 2 1 25
? 2 1 26
? 2 1 27
? 2 1 28
? 2 1 29
? 2 1 30
? 2 2 3
? 2 2 4
? 2 2 5
? 2 2 6
? 2 2 7
? 2 2 8...

result:

ok OK

Test #47:

score: 10
Accepted
time: 0ms
memory: 3600kb

input:

30
23 20
25 9
11 25
3 6
20 28
13 17
27 12
2 22
13 4
14 15
4 28
21 24
2 1
30 6
22 8
27 26
10 21
5 1
30 23
25 16
3 26
11 7
8 10
7 18
15 18
12 9
17 19
29 19
24 14
YES
NO
NO
YES
NO
YES
YES
NO
YES
YES
NO
NO
YES
YES
YES
NO
YES
NO
NO
YES
YES
NO
YES
YES
NO
NO
NO
NO
NO
NO
NO
YES
NO
YES
YES
NO
YES
YES
NO
NO
Y...

output:

? 2 1 2
? 2 1 3
? 2 1 4
? 2 1 5
? 2 1 6
? 2 1 7
? 2 1 8
? 2 1 9
? 2 1 10
? 2 1 11
? 2 1 12
? 2 1 13
? 2 1 14
? 2 1 15
? 2 1 16
? 2 1 17
? 2 1 18
? 2 1 19
? 2 1 20
? 2 1 21
? 2 1 22
? 2 1 23
? 2 1 24
? 2 1 25
? 2 1 26
? 2 1 27
? 2 1 28
? 2 1 29
? 2 1 30
? 2 2 3
? 2 2 4
? 2 2 5
? 2 2 6
? 2 2 7
? 2 2 8...

result:

ok OK

Test #48:

score: 10
Accepted
time: 3ms
memory: 3552kb

input:

30
24 20
9 10
13 10
23 11
14 2
21 27
7 17
28 23
15 1
8 29
19 30
16 18
18 5
29 19
4 12
25 21
9 8
22 17
28 6
30 12
11 16
5 2
22 26
6 15
26 13
7 3
25 7
27 14
24 4
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
...

output:

? 2 1 2
? 2 1 3
? 2 1 4
? 2 1 5
? 2 1 6
? 2 1 7
? 2 1 8
? 2 1 9
? 2 1 10
? 2 1 11
? 2 1 12
? 2 1 13
? 2 1 14
? 2 1 15
? 2 1 16
? 2 1 17
? 2 1 18
? 2 1 19
? 2 1 20
? 2 1 21
? 2 1 22
? 2 1 23
? 2 1 24
? 2 1 25
? 2 1 26
? 2 1 27
? 2 1 28
? 2 1 29
? 2 1 30
? 2 2 3
? 2 2 4
? 2 2 5
? 2 2 6
? 2 2 7
? 2 2 8...

result:

ok OK

Test #49:

score: 10
Accepted
time: 2ms
memory: 3616kb

input:

30
24 27
29 30
12 5
8 6
2 7
17 4
5 16
21 24
4 22
18 9
16 7
11 26
28 13
25 20
10 20
3 15
23 19
10 22
3 19
27 8
25 11
23 6
13 12
18 30
1 21
15 17
2 29
14 28
26 18
NO
YES
YES
NO
YES
NO
YES
YES
YES
YES
NO
NO
NO
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
NO
NO
NO
NO
YES
NO
YES
NO
YES
NO
NO
YES...

output:

? 2 1 2
? 2 1 3
? 2 1 4
? 2 1 5
? 2 1 6
? 2 1 7
? 2 1 8
? 2 1 9
? 2 1 10
? 2 1 11
? 2 1 12
? 2 1 13
? 2 1 14
? 2 1 15
? 2 1 16
? 2 1 17
? 2 1 18
? 2 1 19
? 2 1 20
? 2 1 21
? 2 1 22
? 2 1 23
? 2 1 24
? 2 1 25
? 2 1 26
? 2 1 27
? 2 1 28
? 2 1 29
? 2 1 30
? 2 2 3
? 2 2 4
? 2 2 5
? 2 2 6
? 2 2 7
? 2 2 8...

result:

ok OK

Test #50:

score: 10
Accepted
time: 3ms
memory: 3488kb

input:

30
28 27
7 6
16 13
20 22
12 1
26 27
19 24
19 23
15 6
12 2
5 14
3 25
9 29
26 30
22 29
11 25
10 21
21 18
2 15
7 17
28 20
11 24
13 9
6 4
8 30
5 1
23 10
17 3
8 18
YES
NO
YES
YES
YES
NO
NO
NO
NO
NO
YES
NO
YES
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
YES
YES
NO
NO
NO
NO
NO
YES
NO
YES
YES
NO...

output:

? 2 1 2
? 2 1 3
? 2 1 4
? 2 1 5
? 2 1 6
? 2 1 7
? 2 1 8
? 2 1 9
? 2 1 10
? 2 1 11
? 2 1 12
? 2 1 13
? 2 1 14
? 2 1 15
? 2 1 16
? 2 1 17
? 2 1 18
? 2 1 19
? 2 1 20
? 2 1 21
? 2 1 22
? 2 1 23
? 2 1 24
? 2 1 25
? 2 1 26
? 2 1 27
? 2 1 28
? 2 1 29
? 2 1 30
? 2 2 3
? 2 2 4
? 2 2 5
? 2 2 6
? 2 2 7
? 2 2 8...

result:

ok OK

Test #51:

score: 10
Accepted
time: 3ms
memory: 3488kb

input:

30
6 3
19 25
30 1
11 10
8 15
22 20
8 1
27 30
15 21
11 3
30 17
7 5
18 12
25 2
21 28
26 16
24 10
9 28
29 12
4 22
17 29
7 14
23 2
18 4
13 6
19 9
16 5
23 24
20 26
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
Y...

output:

? 2 1 2
? 2 1 3
? 2 1 4
? 2 1 5
? 2 1 6
? 2 1 7
? 2 1 8
? 2 1 9
? 2 1 10
? 2 1 11
? 2 1 12
? 2 1 13
? 2 1 14
? 2 1 15
? 2 1 16
? 2 1 17
? 2 1 18
? 2 1 19
? 2 1 20
? 2 1 21
? 2 1 22
? 2 1 23
? 2 1 24
? 2 1 25
? 2 1 26
? 2 1 27
? 2 1 28
? 2 1 29
? 2 1 30
? 2 2 3
? 2 2 4
? 2 2 5
? 2 2 6
? 2 2 7
? 2 2 8...

result:

ok OK

Test #52:

score: 10
Accepted
time: 3ms
memory: 3548kb

input:

30
25 26
12 1
13 28
10 13
7 9
4 17
7 6
4 23
6 21
5 16
1 19
25 5
21 29
12 2
15 28
14 3
24 3
16 19
14 2
30 22
8 27
29 18
30 10
15 27
20 22
17 18
27 24
26 23
11 20
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
Y...

output:

? 2 1 2
? 2 1 3
? 2 1 4
? 2 1 5
? 2 1 6
? 2 1 7
? 2 1 8
? 2 1 9
? 2 1 10
? 2 1 11
? 2 1 12
? 2 1 13
? 2 1 14
? 2 1 15
? 2 1 16
? 2 1 17
? 2 1 18
? 2 1 19
? 2 1 20
? 2 1 21
? 2 1 22
? 2 1 23
? 2 1 24
? 2 1 25
? 2 1 26
? 2 1 27
? 2 1 28
? 2 1 29
? 2 1 30
? 2 2 3
? 2 2 4
? 2 2 5
? 2 2 6
? 2 2 7
? 2 2 8...

result:

ok OK

Test #53:

score: 10
Accepted
time: 3ms
memory: 3596kb

input:

30
20 22
9 22
3 23
20 4
24 17
27 13
15 8
1 6
6 19
15 10
25 12
5 10
16 26
29 8
29 2
28 21
23 17
30 25
24 7
1 11
3 12
19 7
16 28
2 14
11 13
14 30
18 26
13 18
21 9
YES
YES
NO
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
NO
YES
NO
YES
NO
NO
NO
YES
YES
YES
NO
YES
NO
YES
YES
YES
NO
YES
YES
YES
YES
NO
YES
YE...

output:

? 2 1 2
? 2 1 3
? 2 1 4
? 2 1 5
? 2 1 6
? 2 1 7
? 2 1 8
? 2 1 9
? 2 1 10
? 2 1 11
? 2 1 12
? 2 1 13
? 2 1 14
? 2 1 15
? 2 1 16
? 2 1 17
? 2 1 18
? 2 1 19
? 2 1 20
? 2 1 21
? 2 1 22
? 2 1 23
? 2 1 24
? 2 1 25
? 2 1 26
? 2 1 27
? 2 1 28
? 2 1 29
? 2 1 30
? 2 2 3
? 2 2 4
? 2 2 5
? 2 2 6
? 2 2 7
? 2 2 8...

result:

ok OK

Subtask #3:

score: 0
Wrong Answer

Test #54:

score: 0
Wrong Answer
time: 4ms
memory: 3652kb

input:

500
419 133
44 225
391 269
419 461
293 347
108 31
110 363
423 257
321 155
498 87
180 492
251 5
357 30
341 172
275 109
372 446
286 336
208 339
162 320
138 103
129 219
62 141
359 286
130 238
470 460
418 48
210 358
429 13
323 143
382 415
406 394
309 175
325 170
128 108
6 113
363 17
470 457
7 224
288 48...

output:

? 2 1 2
? 2 1 3
? 2 1 4
? 2 1 5
? 2 1 6
? 2 1 7
? 2 1 8
? 2 1 9
? 2 1 10
? 2 1 11
? 2 1 12
? 2 1 13
? 2 1 14
? 2 1 15
? 2 1 16
? 2 1 17
? 2 1 18
? 2 1 19
? 2 1 20
? 2 1 21
? 2 1 22
? 2 1 23
? 2 1 24
? 2 1 25
? 2 1 26
? 2 1 27
? 2 1 28
? 2 1 29
? 2 1 30
? 2 1 31
? 2 1 32
? 2 1 33
? 2 1 34
? 2 1 35
? ...

result:

wrong output format Unexpected end of file - int32 expected