题目背景

正在打集的 Displace_ 瞅了一眼U群，发现大家在讨论 NPC 问题，看着集成战略的地图，他突然想到了一个经典 NPC 问题：图染色。

经典的图染色问题是一个 $n$ 个点 $m$ 条边的无向连通图，用 $k$ 种颜色来给每个点染色，使得任意有边连接的两个点颜色不同，构造一个方案。

$k=1$ 是简单的，当 $k=2$ 时问题的难度就骤增了，所以仁慈的 Displace_ 保证 $k\leq 3$。

但即使是 $k=3$ 的问题，在边较多的图上也是及其棘手的，所以 Displace_ 保证图的边数不多，具体的，有一个阈值 $t$，保证 $m\leq n+t$。

被邪魔污染的 Displace_ 决定就限制这么多条件，现在你需要在这样的条件下构造出一个染色方案，或者报告无解。

输入格式

第一行一个整数 $taskid$，表示测试点编号，$taskid=0$ 表示该测试点为样例。

接下来一行四个整数 $n,m,k,t$，表示图的点数、边数，允许使用的颜色数和阈值。

接下来 $m$ 行，每行两个整数 $x, y$，表示有一条连接 $x,y$ 的边。

输出格式

如果无解，输出一行 -1。

否则在第一行输出 1，在接下来的一行输出 $n$ 个正整数，第 $i$ 个整数 $c_i$ 表示 $i$ 号节点的颜色，你需要保证 $\forall c_i\leq k,\forall_{(x,y)\in E}c_x\neq c_y$。

样例输入

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

样例输出

1
2 1 3 2 3

数据范围与时空限制

1s，512MB

对于所有测试点，保证 $n\leq 1e5,k\leq 3,-1\leq t\leq 8,n-1\leq m\leq n+t$，保证图联通，图中无自环无重边,。

因为一些原因，本题采用subtask捆绑测试，数据的参数 $taskid$ 与其所属的子任务编号相同。

subtask1(1pts):$k= 1$。

subtask2(9pts):$k= 2$。

subtask3(15pts):$k=3,n\leq 15$。

subtask4(10pts):$k=3,t= -1$。

subtask5(20pts):$k=3,t = 0$。

subtask6(45pts):$k=3,$ 无其他特殊限制。