A. Rikka with Minimum Spanning Trees

Description:

Hello everyone! I am your old friend Rikka. Welcome to Xuzhou. This is the first problem, which is a problem about the minimum spanning tree (MST). I promise you all that this should be the easiest problem for most people.
A minimum spanning tree, or minimum weight spanning tree, is a subset of edges from an edge-weighted undirected graph, which forms a tree with the minimum possible total edge weight that connects all the vertices together without any cycles.
In this problem, Rikka wants you to calculate the summation of total edge weights through all MSTs for a given graph, which obviously equals to the product of the total edge weight in an MST and the total number of different MSTs. Note that two spanning trees are different if the sets of their edges are different. In addition, a disconnected graph could have no MSTs, the number of whose different MSTs is zero.
To decrease the size of the input, Rikka provides an edge-weighted undirected graph via a random number generator with given random seeds, denoted by two integers $k_1$k1​ and $k_2$k2​. Supposing the number of vertices and edges in the graph are $n$n and $m$m respectively, the following code in C++ tells you how to generate the graph and store the $i$i-th edge between the vertex $u\left[i\right]$u[i] and $v\left[i\right]$v[i] with weight $w\left[i\right]$w[i] in corresponding arrays. You can use the code directly in your submissions.

Also, to decrease the size of the output, your code should output the answer modulo $(10^9+7)$(109+7).
If you have already learned how to handle that, start your show and omit all the rest of the statement.
To make sure everyone knows how to solve this problem, here Rikka would like to provide for you all an effective practice which can solve the problem and help you all get Accepted!
The first one you need to know is the Kirchhoff’s matrix tree theorem. Given an undirected graph $G$G with $n$n vertices excluding all loops, its Laplacian matrix $L_{n\times n}$Ln×n​ is defined as $(D-A)$(D−A), where $D$D is the degree matrix and $A$A is the adjacency matrix of the graph. More precisely, in the matrix $L$L the entry $l_{i,j}$li,j​ ( $i\ne j$i̸​=j) equals to $-m$−m where $m$m is the number of edges between the $i$i-th vertex and the $j$j-th vertex, and $L_{i,i}$Li,i​ equals to the degree of the $i$i-th vertex. Next, construct a matrix $L^{\ast }$L∗ by deleting any row and any column from $L$L, for example, deleting row $1$1 and column $1$1. The Kirchhoff’s matrix tree theorem shows that the number of spanning trees is exactly the determinant of $L^{\ast }$L∗, which can be computed in polynomial time.
Now let me explain an algorithm that counts the number of MSTs. The algorithm breaks up the Kruskal’s algorithm for MST into a series of blocks, each of which consists of a sequence of operations about adding edges in a same weight into a multigraph (where a multigraph is a graph, two vertices of which may be connected by more than one edge) whose vertices are components that have been built through the previous block of operations.
Precisely speaking, let’s label the multigraph that has been built after the $i$i-th block of operations as $G_i$Gi​. Without loss of generality, let’s consider the $0$0-th block which has no operation and let $G_0$G0​ be an empty graph with $n$n isolated vertices. The $i$i-th block of operations squeezes vertices in $G_{i-1}$Gi−1​ connected by edges in this block into a single vertex. The result is exactly the graph $G_i$Gi​.
If you know the cardinal principle of Kruskal’s algorithm pretty well, you may find that the number of MSTs is the product of the numbers of spanning trees in every component of the graph for each block-defining weight. Actually, the number of edges for a certain weight is fixed in all MSTs, based on the greedy-choice strategy in Kruskal’s algorithm. Finally, the Kirchhoff’s matrix tree theorem helps you compute the numbers of spanning trees for graphs.

Input:

The input contains several test cases, and the first line contains a single integer $T$T ( $1\le T\le 100$1≤T≤100), the number of test cases.
For each test case, the only line contains four integers $n$n $(1\le n\le 10^5)$(1≤n≤105), $m$m ( $m=10^5$m=105), $k_1$k1​ and $k_2$k2​ ( $10^8\le k_1,k_2\le 10^{12}$108≤k1​,k2​≤1012), where $k_1$k1​ and $k_2$k2​ are chosen randomly except for the sample.

Output:

For each test case, output a single line with a single number, the answer modulo $(10^9+7)$(109+7).

Sample Input:

1
2 100000 123456789 987654321

Sample Output:

575673759

题目链接

现场赛的时候题目根本就没有看懂，只知道题目上有说MST，然后随机代码也很明显的给出了u[i]、v[i]、w[i]，所以队友就直接开敲Kruskal了，队友建边时没用unsigned long long，用的int，所以现场整整两个小时才写出来，写出来之后另一个队友偷听隔壁"拉格朗"说没判不存在生成树的情况WA了一发，就赶紧写上判断，提交(121min)1A(我比赛全程没碰键盘?)。

这道题目由于是随机数据，所以可以直接跑最小生成树(大佬实现题目算法也没问题)，注意特判不存在生成树的情况并输出0、Kruskal并查集不压缩路径会TLE。

AC代码:

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

const int mod = 1e9 + 7;
const int maxn = 1e5 + 5;

struct Edge {
    int u, v;
    unsigned long long weight;

    bool operator < (const Edge &b) const {
        return weight < b.weight;
    }
};

int pre[maxn];
bool vis[maxn];
Edge edges[maxn];

unsigned long long k1, k2;

unsigned long long xorShift128Plus() {
    unsigned long long k3 = k1, k4 = k2;
    k1 = k4;
    k3 ^= k3 << 23;
    k2 = k3 ^ k4 ^ (k3 >> 17) ^ (k4 >> 26);
    return k2 + k4;
}

int n, m, u[maxn], v[maxn];
unsigned long long w[maxn];

void init() {
    for (int i = 0; i <= n; ++i) {
        pre[i] = i;
        vis[i] = false;
    }
}

int find(int x) {
    int r = x;
    while (pre[r] != r) {
        r = pre[r];
    }
    int i = x, j;
    while (i != r) {
        j = pre[i];
        pre[i] = r;
        i = j;
    }
    return r;
}

void join(int x, int y) {
    int xx = find(x);
    int yy = find(y);
    if (xx != yy) {
        pre[xx] = yy;
    }
}

unsigned long long kruskal() {
    sort(edges + 1, edges + m + 1);
    init();
    unsigned long long ans = 0;
    for (int i = 1; i <= m; ++i) {
        if (find(edges[i].u) != find(edges[i].v)) {
            join(edges[i].u, edges[i].v);
            ans = (ans + edges[i].weight) % mod;
            vis[edges[i].u] = true;
            vis[edges[i].v] = true;
        }
    }
    return ans;
}

void gen() {
    scanf("%d%d%llu%llu", &n, &m, &k1, &k2);
    for (int i = 1; i <= m; ++i) {
        u[i] = xorShift128Plus() % n + 1;
        v[i] = xorShift128Plus() % n + 1;
        w[i] = xorShift128Plus();
        edges[i] = Edge {u[i], v[i], w[i]};
    }
}

bool check() {
    for (int i = 1; i <= n; ++i) {
        if (!vis[i]) {
            return false;
        }
    }
    return true;
}

int t;
unsigned long long ans;

int main(int argc, char *argv[]) {
    scanf("%d", &t);
    while (t--) {
        gen();
        ans = kruskal();
        printf("%llu\n", check() ? ans : 0);
    }
    return 0;
}

C. Rikka with Consistency

Description:

On the way to the Moscow, Rikka knows someone will replace her. Who is the guy? A devil to get in touch with her dark side, or an angel to rinse the shadow off her mind? However, Rikka knows that her successor has a special name, whose meaning in Chinese is Consistency. The process of replacement is so wonderful and sentimental, which is what you all must know.
Now, the only road from Beijing to Moscow is described as a broken line with $n$n segments in the $X$X- $H$H plane. The $i$i-th segment connects the points $(i-1,h_{i-1})$(i−1,hi−1​) and $(i,h_i)$(i,hi​), and $h_0=h_n=0$h0​=hn​=0 are known. This figure is a topographic map showing the whole trip from Beijing to Moscow and its $H$H axis indicates the altitude. The distance of a path between two points is the length of the broken line between their corresponding points in the map.
At the outset of the trip, Rikka is in Beijing whose location in the $X$X- $H$H plane is $(0,0)$(0,0); Consistency, the guy who will replace Rikka, is in Moscow which is located at $(n,0)$(n,0). Consistency always maintains consistent academic standards, a consistent life level, a consistent height of perspective and the altitude as what Rikka owns. This is why their heights are the same yesterday, today and forever.
Now Rikka wants you to calculate the minimum total distance they need (which is the total length of paths that Rikka and Consistency travel along). By the time that Rikka arrives in Moscow and Consistency arrives in Beijing as well, their replacement will be finished (and this is the ending which is also a new beginning).

Input:

The input contains several test cases, and the first line contains a single integer $T$T ( $1\le T\le 500$1≤T≤500), the number of test cases.
For each test case, the first line contains a single integer $n$n ( $1\le n\le 50$1≤n≤50), the number of segments.
The second line contains $(n+1)$(n+1) integers h0​,h1​,⋯,hn​ ( $0\le h_i\le 50$0≤hi​≤50), satisfying $h_0=h_n=0$h0​=hn​=0.
The input guarantees that the paths for each test case always exist.

Output:

For each test case, output a single line with a single number, the minimum total distance they need. Your answer is considered correct if its absolute or relative error does not exceed $10^{-9}$10−9. Formally, let your answer be $a$a, and Rikka’s answer be $b$b. Your answer is considered correct if $\frac{\mid a-b\mid }{\max (1,\mid b\mid )}\le 10^{-9}$max(1,∣b∣)∣a−b∣​≤10−9.

Sample Input:

2
4
0 1 1 2 0
4
0 2 1 3 0

Sample Output:

12.128990204491960
22.313624568639947

题目链接

这道题目和2010年Tokyo区域赛E题几乎一样(UVAlive5071、Aizu1309)，只是乘了二倍，具体请看

Aizu 1309 The Two Men of the Japanese Alps

AC代码:

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

const int maxn = 2e3 + 5;

struct Point {
    double X, Y;

    void Output() {
        printf("(%lf,%lf)\n", X, Y);
    }

    Point operator - (const Point &B) const {
        return Point {X - B.X, Y - B.Y};
    }

    double operator * (const Point &B) const {
        return X * B.X + Y * B.Y;
    }

    double operator ^ (const Point &B) const {
        return X * B.Y - Y * B.X;
    }

    bool operator < (const Point &B) const {
        return X < B.X;
    }
};

double Distance(Point A, Point B) {
    return sqrt((B - A) * (B - A));
}

struct Line {
    Point S, T;

    Point operator & (const Line &B) const {
        double Temp = ((S - B.S) ^ (B.S - B.T)) / ((S - T) ^ (B.S - B.T));
        return Point {S.X + (T.X - S.X) * Temp, S.Y + (T.Y - S.Y) * Temp};
    }
};

struct Status {
    int Left, Right;
    double Length;

    bool operator < (const Status &B) const {
        return Length > B.Length;
    }
};

int T;
int N;
int Tot;
int Height[maxn];
Point points[maxn];

void Init() {
    for (int i = 0; i <= N; ++i) {
        Line SkyLine = Line {Point {-1.0, points[i].Y}, Point {55.0, points[i].Y}};
        for (int j = 0; j < N; ++j) {
            if ((points[i].Y - points[j].Y) * (points[i].Y - points[j + 1].Y) < 0) {
                points[Tot++] = SkyLine & Line {points[j], points[j + 1]};
            }
        }
    }
    sort(points, points + Tot);
}

bool Vis[maxn][maxn];

double Bfs() {
    memset(Vis, false, sizeof(Vis));
    priority_queue<Status> Que;
    Que.push(Status {0, Tot - 1, 0.0});
    while (!Que.empty()) {
        Status Cur = Que.top(); Que.pop();
        if (Cur.Left == Cur.Right) {
            return Cur.Length;
        }
        if (Vis[Cur.Left][Cur.Right]) {
            continue;
        }
        Vis[Cur.Left][Cur.Right] = true;
        for (int i = -1; i < 2; ++i) {
            for (int j = -1; j < 2; ++j) {
                if (i || j) {
                    int LeftIndex = Cur.Left + i, RightIndex = Cur.Right + j;
                    if (LeftIndex >= 0 && LeftIndex < Tot && RightIndex >= 0 && RightIndex < Tot) {
                        if (points[LeftIndex].Y == points[RightIndex].Y) {
                            Que.push(Status {LeftIndex, RightIndex, Cur.Length + Distance(points[Cur.Left], points[LeftIndex]) + Distance(points[Cur.Right], points[RightIndex])});
                        }
                    }
                }
            }
        }
    }
    return 0.0;
}

int main(int argc, char *argv[]) {
    scanf("%d", &T);
    for (int Case = 1; Case <= T; ++Case) {
        scanf("%d", &N);
        Tot = 0;
        for (int i = 0; i <= N; ++i) {
            scanf("%d", &Height[i]);
            points[Tot++] = Point {double(i), double(Height[i])};
        }
        Init();
        printf("%.15lf\n", Bfs() * 2);
    }
    return 0;
}

G. Rikka with Intersections of Paths

Description:

Rikka has a tree $T$T with $n$n vertices numbered from $1$1 to $n$n.
Meanwhile, Rikka has marked $m$m simple paths in $T$T, the $i$i-th of which is between the vertices $x_i$xi​ and $y_i$yi​, where some of them could be the same path.
Now, Rikka wants to know in how many different strategies she can select $k$k paths from the marked paths such that those selected paths share at least one common vertex.

Input:

The input contains several test cases, and the first line contains a single integer $T$T ( $1\le T\le 200$1≤T≤200), the number of test cases.
For each test case, the first line contains three integers $n$n ( $1\le n\le 3\times 10^5$1≤n≤3×105), the size of the tree $T$T, $m$m ( $2\le m\le 3\times 10^5$2≤m≤3×105), the number of marked paths, and $k$k ( $2\le k\le m$2≤k≤m).
The following $(n-1)$(n−1) lines describe the tree $T$T. Each of them contains two integers $u$u and $v$v ( $1\le u,v\le n$1≤u,v≤n, $u\ne v$u̸​=v), representing an edge between the vertices $u$u and $v$v.
The following $m$m lines describe all marked simple paths in the tree. The $i$i-th of them contains two integers $x_i$xi​ and $y_i$yi​ ( $1\le x_i,y_i\le n$1≤xi​,yi​≤n).
The input guarantees that the sum of $n$n and the sum of $m$m in all test cases are at most $2\times 10^6$2×106 respectively.

Output:

For each test case, output a single line with a single integer, the number of different strategies meeting the requirement modulo $(10^9+7)$(109+7).

Sample Input:

1
3 6 2
1 2
1 3
1 1
2 2
3 3
1 2
1 3
2 3

Sample Output:

10

题目链接

这道题目和hihoCoder#1167 : 高等理论计算机科学有些类似，都是求的相交路径数量，只不过这道题目问的是k条路径相交的数量，求出LCA之后枚举顶点，用数学做法计算每个顶点的贡献即可。

$ans+=C_{cnt\left[i\right]}^k-C_{cnt\left[i\right]-LCAcnt\left[i\right]}^k$ans+=Ccnt[i]k​−Ccnt[i]−LCAcnt[i]k​，其中 $cnt\left[i\right]$cnt[i]为经过顶点 $i$i的路径数量（通过树上差分计算）， $LCAcnt\left[i\right]$LCAcnt[i]为 $LCA$LCA是 $i$i顶点的路径数量。

AC代码:

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

const long long mod = 1e9 + 7;
const int maxn = 3e5 + 5;

struct Edge {
    int V, Next;
};

Edge edges[maxn << 4];
int Head[maxn];
int Tot;

void AddEdge(int U, int V) {
    edges[Tot] = Edge {V, Head[U]};
    Head[U] = Tot++;
}

int Rmq[maxn << 1];

struct ST {
    int Dp[maxn << 1][20];
    void Init(int N) {
        for (int i = 1; i <= N; ++i) {
            Dp[i][0] = i;
        }
        for (int j = 1; (1 << j) <= N; ++j) {
            for (int i = 1; i + (1 << j) - 1 <= N; ++i) {
                Dp[i][j] = Rmq[Dp[i][j - 1]] < Rmq[Dp[i + (1 << (j - 1))][j - 1]] ? Dp[i][j - 1] : Dp[i + (1 << (j - 1))][j - 1];
            }
        }
    }

    int Query(int A, int B) {
        if (A > B) {
            swap(A, B);
        }
        int Len = (int)(log2(B - A + 1));
        return Rmq[Dp[A][Len]] < Rmq[Dp[B - (1 << Len) + 1][Len]] ? Dp[A][Len] : Dp[B - (1 << Len) + 1][Len];
    }
};

int Vertex[maxn << 1];
int First[maxn];
int Cnt;
ST St;
int Parent[maxn];

void LCADfs(int Cur, int Pre, int Depth) {
    Vertex[++Cnt] = Cur;
    First[Cur] = Cnt;
    Rmq[Cnt] = Depth;
    Parent[Cur] = Pre;
    for (int i = Head[Cur]; ~i; i = edges[i].Next) {
        if (edges[i].V == Pre) {
            continue;
        }
        LCADfs(edges[i].V, Cur, Depth + 1);
        Vertex[++Cnt] = Cur;
        Rmq[Cnt] = Depth;
    }
}

void LCAInit(int N) {
    Cnt = 0;
    LCADfs(1, 0, 0);
    St.Init(2 * N - 1);
}

int QueryLCA(int U, int V) {
    return Vertex[St.Query(First[U], First[V])];
}

long long Factorial[maxn];
long long InvFactorial[maxn];

long long QuickPow(long long A, long long B) {
    long long Ans = 1;
    while (B) {
        if (B & 1) {
            Ans = Ans * A % mod;
        }
        A = A * A % mod;
        B >>= 1;
    }
    return Ans;
}

void FactorialInit(int N) {
    Factorial[0] = 1;
    for (long long i = 1; i <= N; ++i) {
        Factorial[i] = (Factorial[i - 1] * i) % mod;
    }
    InvFactorial[N] = QuickPow(Factorial[N], mod - 2);
    for (long long i = N - 1; ~i; --i) {
        InvFactorial[i] = (InvFactorial[i + 1] * (i + 1)) % mod;
    }
}

long long C(int N, int M) {
    if (M > N || M < 0 || N < 0) {
        return 0;
    }
    return Factorial[N] * InvFactorial[M] % mod * InvFactorial[N - M] % mod;
}

int Count[maxn];
int LCACount[maxn];

int T;
int N, M, K;
long long Ans;

int Dfs(int Cur, int Pre) {
    for (int i = Head[Cur]; ~i; i = edges[i].Next) {
        if (edges[i].V == Pre) {
            continue;
        }
        Count[Cur] += Dfs(edges[i].V, Cur);
    }
    if (LCACount[Cur]) {
        Ans += ((C(Count[Cur], K) - C(Count[Cur] - LCACount[Cur], K)) + mod) % mod;
        Ans %= mod;
    }
    return Count[Cur];
}

void Init(int N) {
    Tot = 0;
    memset(Head, -1, sizeof(Head));
    for (int i = 1; i <= N; ++i) {
        Count[i] = 0;
        LCACount[i] = 0;
    }
}

int main(int argc, char *argv[]) {
    FactorialInit(maxn - 5);
    scanf("%d", &T);
    for (int Case = 1; Case <= T; ++Case) {
        scanf("%d%d%d", &N, &M, &K);
        Init(N);
        for (int i = 1, U, V; i < N; ++i) {
            scanf("%d%d", &U, &V);
            AddEdge(U, V);
            AddEdge(V, U);
        }
        Parent[1] = 0;
        LCAInit(N);
        for (int i = 1, U, V; i <= M; ++i) {
            scanf("%d%d", &U, &V);
            int LCA = QueryLCA(U, V);
            LCACount[LCA]++;
            Count[U]++; Count[V]++;
            Count[LCA]--; Count[Parent[LCA]]--;
        }
        Ans = 0;
        Dfs(1, 0);
        printf("%lld\n", Ans);
    }
    return 0;
}

M. Rikka with Illuminations

Description:

Rikka loves convex polygons, so she decides to install some illuminants to embellish polygons.
Now she has a large convex polygon with $n$n sides. She also has $m$m different points strictly outside the polygon which are all legal positions to install illuminants.
An illuminant can light up some exterior boundaries of the polygon.
Rikka wants to install some illuminants to light up all exterior boundaries of the polygon. She asks you to calculate the least number of illuminants which she needs and provide a feasible scheme.

Input:

The input contains several test cases, and the first line contains a single integer $T$T ( $1\le T\le 100$1≤T≤100), the number of test cases.
For each test case, the first line contains two integers $n$n ( $3\le n\le 1000$3≤n≤1000) and $m$m ( $1\le m\le 1000$1≤m≤1000).
Each of the following $n$n lines describes a vertex on the convex polygon with two integers $x$x and $y$y ( $\mid x\mid ,\mid y\mid \le 10^9$∣x∣,∣y∣≤109), the Cartesian coordinates of the vertex. All these vertices are given in counter-clockwise order and any three of them are not collinear.
Then the following $m$m lines contain $m$m different points outside the polygon describing all legal positions to install illuminants. Each of them contains two integers $x$x and $y$y ( $\mid x\mid ,\mid y\mid \le 10^9$∣x∣,∣y∣≤109), the Cartesian coordinates of a legal position. They are numbered from $1$1 to $m$m. All these positions would not lie in some extension lines for the sides of the polygon.

Output

For each test case, if it’s impossible to light up all exterior boundaries of the polygon, output a single line with a single integer $-1$−1. Otherwise, output two lines. Firstly, output a line with a single integer $k$k, representing the least number of illuminants Rikka needs to light up all the boundaries. Then, output a line with $k$k space-separated distinct integers, describing a feasible scheme, each of which is the index of a selected position.
All feasible schemes are allowed, so you can output any of them.

Sample Input:

1
3 3
0 0
1 0
0 1
-1 -1
3 -1
-1 3

Sample Output:

2
2 1

题目链接

给出一个 $n$n 个点组成的凸包和凸包外的 $m$m 个光源，求用最少光源照亮凸包所有区域方案。

这个题目可以分为两个相对独立的问题解决：

1. 求每个光源可以照亮的区域段
2. 求最少光源的组成方案

首先看第一个问题，求每个光源的可照亮区域段。

将凸包以其 $n$n 个节点划分为 $n$n 段，枚举光源利用叉乘判断光源照亮的区域段，具体是先找照亮区域段的下界，之后再往后依次找上界，将所有光源的区域段存储。

求出每个光源的可照亮区域段之后就可以进行第二个问题，求最少光源的组成方案。

枚举每个光源作为必选点，一次向后贪心找下一个光源点，记录最少光源数的方案即可。

AC代码:

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

typedef double db;
const int maxn = (int)(1e3 + 5);
const db eps = 1e-8;

int Sgn(db Key) {return fabs(Key) < eps ? 0 : (Key < 0 ? -1 : 1);};
struct Point {db X, Y;};
typedef Point Vector;
Vector operator + (Vector Key1, Vector Key2) {return (Vector){Key1.X + Key2.X, Key1.Y + Key2.Y};};
Vector operator - (Vector Key1, Vector Key2) {return (Vector){Key1.X - Key2.X, Key1.Y - Key2.Y};};
db operator * (Vector Key1, Vector Key2) {return Key1.X * Key2.X + Key1.Y * Key2.Y;};
db operator ^ (Vector Key1, Vector Key2) {return Key1.X * Key2.Y - Key1.Y * Key2.X;};

bool Check(Vector Key1, Vector Key2, Vector Key3) {
    if (Sgn(Key1 ^ Key2) >= 0 && Sgn(Key2 ^ Key3) >= 0) return false;
    if (Sgn(Key1 ^ Key2) <= 0 && Sgn(Key2 ^ Key3) <= 0) return false;
    return true;
}

struct Interval {int Left, Right, Id;};
bool operator < (Interval &Key1, Interval &Key2) {return Key1.Left == Key2.Left ? Key1.Right > Key2.Right : Key1.Left < Key2.Left;}

int T;
int N, M;
Point Polygon[maxn];
Point Light[maxn];
int Tot;
Interval Section[maxn];
vector<int> Ans, Buffer;

void Divide() {
    Tot = 0;
    for (int i = 0; i < M; ++i) {
        int Left = 0;
        for (int j = 0; j < N; ++j)
            if (Sgn((Polygon[(j + 1) % N] - Polygon[j]) ^ (Polygon[j] - Light[i])) > 0 && Sgn((Polygon[j] - Polygon[(j - 1 + N) % N]) ^ (Polygon[(j - 1 + N) % N] - Light[i])) <= 0) Left = j;
        int Right = Left;
        while (Right <= N + Left) {
            if (Sgn((Polygon[(Right + 1) % N] - Polygon[Right % N]) ^ (Polygon[Right % N] - Light[i])) <= 0) break;
            Right++;
        }
        Section[Tot++] = (Interval){Left, Right, i};
    }
    sort(Section, Section + Tot);
}

void Select() {
    Ans.clear();
    for (int Start = 0; Start < Tot; ++Start) {
        Buffer.clear();
        int Cur = Start;
        Buffer.push_back(Section[Cur].Id);
        while (Section[Cur].Right < Section[Start].Left + N) {
            int Last = Section[Cur].Right;
            for (int j = Start + 1; j < Tot && Section[j].Left <= Last; ++j) {
                if (Section[j].Right > Section[Cur].Right) Cur = j;
            }
            if (Section[Cur].Right == Last) break;
            Buffer.push_back(Section[Cur].Id);
        }
        if (Section[Cur].Right >= Section[Start].Left + N && ((int)Ans.empty() || (int)Buffer.size() < (int)Ans.size())) Ans.assign(Buffer.begin(), Buffer.end());
    }
}

int main(int argc, char *argv[]) {
    scanf("%d", &T);
    for (int Case = 1; Case <= T; ++Case) {
        scanf("%d%d", &N, &M);
        for (int i = 0; i < N; ++i) scanf("%lf%lf", &Polygon[i].X, &Polygon[i].Y);
        for (int i = 0; i < M; ++i) scanf("%lf%lf", &Light[i].X, &Light[i].Y);
        Divide();
        Select();
        if (Ans.empty()) printf("-1\n");
        else {
            printf("%d\n%d", (int)Ans.size(), Ans[0] + 1);
            for (int i = 1; i < (int)Ans.size(); ++i) {
                printf(" %d", Ans[i] + 1);
            }
            printf("\n");
        }
    }
    return 0;
}