#include "grader.h"
#include "encoder.h"
#include <bits/stdc++.h>
using namespace std;
// macros
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> lll;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<lll> vlll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define FOR(a,b) for(auto& a : b)
#define all(a) a.begin(), a.end()
#define INF 1e9
#define EPS 1e-9
#define pb push_back
#define popb pop_back
#define fi first
#define se second
void writeSmallInt(int x, int bits) {
RE(i,bits) {
bool b = false;
if(x & (1<<i)) b = 1;
encode_bit(b);
}
}
int maxBits(int x) {
int mx = 0;
RE(i,10) if(x&(1<<i)) mx = max(mx, i+1);
return mx;
}
void encode(int nv, int nh, int ne, int *v1, int *v2) {
vector<vi> adj; adj.resize(nv);
set<ii> difEdges;
RE(i,ne) {
adj[v1[i]].pb(v2[i]);
adj[v2[i]].pb(v1[i]);
difEdges.insert({v1[i],v2[i]});
difEdges.insert({v2[i],v1[i]});
}
set<ii> usedEdges;
RE(h,nh) {
// bfs
vi dist; dist.assign(nv, -1);
queue<int> q;
q.push(h); dist[h] = 0;
while(!q.empty()) {
int u = q.front(); q.pop();
FOR(v,adj[u]) {
if(dist[v] != -1) continue;
dist[v] = dist[u] + 1;
q.push(v);
}
}
vi prev = {h};
RE1(i,nv) {
vi cur;
RE(u,nv) if(dist[u] == i) cur.pb(u);
FOR(u,cur) {
bool found = false;
FOR(v,prev) if(usedEdges.count({min(u,v),max(u,v)})) {
found = true;
break;
}
if(!found) FOR(v,prev) if(difEdges.count({u,v})) {
usedEdges.insert({min(u,v),max(u,v)});
break;
}
}
if(cur.empty()) break;
prev = cur;
}
}
RE(i,nv) adj[i].clear();
FOR(p,usedEdges) adj[p.se].pb(p.fi);
RE(i,nv) {
writeSmallInt(adj[i].size(), 10);
int minBits = maxBits(i-1);
if(minBits * adj[i].size() <= i-1) {
FOR(v,adj[i]) writeSmallInt(v, minBits);
} else {
bitset<1000> bs; bs.reset();
FOR(v,adj[i]) bs[v] = 1;
RE(v,i) encode_bit(bs[v]);
}
}
}
#include "grader.h"
#include "decoder.h"
#include <bits/stdc++.h>
using namespace std;
// macros
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> lll;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<lll> vlll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define FOR(a,b) for(auto& a : b)
#define all(a) a.begin(), a.end()
#define INF 1e9
#define EPS 1e-9
#define pb push_back
#define popb pop_back
#define fi first
#define se second
int readSmallInt(int bits) {
int res = 0;
RE(i,bits) {
bool b = decode_bit();
if(b) res |= (1<<i);
}
return res;
}
int maxBits(int x) {
int mx = 0;
RE(i,10) if(x&(1<<i)) mx = max(mx, i+1);
return mx;
}
void decode(int nv, int nh) {
// reconstruct graph
vector<vi> adj; adj.resize(nv);
RE(u,nv) {
int sz = readSmallInt(10);
int minBits = maxBits(u-1);
if(minBits * sz <= u-1) {
RE(j,sz) {
int v = readSmallInt(minBits);
adj[u].pb(v);
adj[v].pb(u);
}
} else {
RE(v,u) if(decode_bit()) adj[u].pb(v), adj[v].pb(u);
}
}
RE(h,nh) {
// bfs
vi dist; dist.assign(nv, -1);
queue<int> q;
q.push(h); dist[h] = 0;
while(!q.empty()) {
int u = q.front(); q.pop();
hops(h,u,dist[u]);
FOR(v,adj[u]) {
if(dist[v] != -1) continue;
dist[v] = dist[u] + 1;
q.push(v);
}
}
}
}
