結果
| 問題 | No.1044 正直者大学 |
| ユーザー |
 Suunn
|
| 提出日時 | 2019-11-13 16:49:27 |
| 言語 | Java21 (openjdk 21) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 37,202 bytes |
| コンパイル時間 | 3,957 ms |
| コンパイル使用メモリ | 97,640 KB |
| 実行使用メモリ | 46,484 KB |
| 最終ジャッジ日時 | 2024-11-23 05:35:24 |
| 合計ジャッジ時間 | 9,488 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | WA | - |
| testcase_01 | AC | 145 ms
46,100 KB |
| testcase_02 | AC | 140 ms
46,080 KB |
| testcase_03 | AC | 148 ms
46,216 KB |
| testcase_04 | AC | 147 ms
46,168 KB |
| testcase_05 | AC | 149 ms
46,176 KB |
| testcase_06 | AC | 168 ms
45,856 KB |
| testcase_07 | AC | 153 ms
46,072 KB |
| testcase_08 | AC | 145 ms
46,220 KB |
| testcase_09 | WA | - |
| testcase_10 | WA | - |
| testcase_11 | WA | - |
| testcase_12 | AC | 148 ms
46,100 KB |
| testcase_13 | AC | 159 ms
46,192 KB |
| testcase_14 | AC | 137 ms
44,756 KB |
| testcase_15 | AC | 152 ms
46,192 KB |
| testcase_16 | WA | - |
| testcase_17 | AC | 157 ms
46,092 KB |
| testcase_18 | AC | 155 ms
46,096 KB |
| testcase_19 | WA | - |
| testcase_20 | AC | 148 ms
46,240 KB |
| testcase_21 | WA | - |
| testcase_22 | AC | 135 ms
44,880 KB |
| testcase_23 | AC | 144 ms
46,080 KB |
| testcase_24 | AC | 145 ms
46,484 KB |
| testcase_25 | AC | 141 ms
45,936 KB |
| testcase_26 | AC | 149 ms
46,276 KB |
| testcase_27 | AC | 148 ms
46,100 KB |
| testcase_28 | AC | 146 ms
45,900 KB |
| testcase_29 | WA | - |
ソースコード
import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.NoSuchElementException;
import java.util.Objects;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Random;
import java.util.Scanner;
import java.util.TreeMap;
import java.util.TreeSet;
import java.util.function.BiFunction;
public class Main{
static Scanner scn = new Scanner(System.in);
static FastScanner sc = new FastScanner();
static Mathplus mp = new Mathplus();
static PrintWriter ot = new PrintWriter(System.out);
static Random rand = new Random();
static int mod = 1000000007;
static long inf = (long)1e17;
static int[] dx = {0,1,0,-1};
static int[] dy = {1,0,-1,0};
public static void main(String[] args) {
int M = sc.nextInt();
int N = sc.nextInt();
int K = sc.nextInt();
int kyoyou = N+M-K;
long ans = 0;
mp.buildFacn(250000);
long base = mp.fac[N-1];
for(int i=1;i*2<=kyoyou;i++) {
if(N>=i) {
long pos = mp.comb(N,i);
if(M>i) {
long dis = mp.comb(M-1,i-1);
ans += base * pos % mod * dis % mod * mp.fac[M] % mod;
ans %= mod;
}
}
}
System.out.println(ans);
}
}
class GridGraph extends Graph{
int N;
int M;
String[] S;
HashMap<Character,Integer> map;
GridGraph(int n,int m,String[] s,char[] c){
super(n*m);
N = n;
M = m;
S = s;
map = new HashMap<Character,Integer>();
for(int i=0;i<n-1;i++) {
for(int j=0;j<m;j++) {
if(S[i].charAt(j)!='#'&&S[i+1].charAt(j)!='#') {
addEdge(toint(i,j),toint(i+1,j));
addEdge(toint(i+1,j),toint(i,j));
}
}
}
for(int i=0;i<n;i++) {
for(int j=0;j<m-1;j++) {
if(S[i].charAt(j)!='#'&&S[i].charAt(j+1)!='#') {
addEdge(toint(i,j),toint(i,j+1));
addEdge(toint(i,j+1),toint(i,j));
}
}
}
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
for(int k=0;k<c.length;k++) {
if(S[i].charAt(j)==c[k])map.put(c[k],toint(i,j));
}
}
}
}
int toint(int i,int j) {
return i*M+j;
}
}
class BetterGridGraph{
int N;
int M;
char[][] S;
HashMap<Character,Integer> map;
int[] dx = {0,1,0,-1};
int[] dy = {1,0,-1,0};
char w;
char b = '#';
BetterGridGraph(int n,int m,String[] s,char[] c){
N = n;
M = m;
for(int i=0;i<s.length;i++) {
S[i] = s[i].toCharArray();
}
map = new HashMap<Character,Integer>();
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
for(int k=0;k<c.length;k++) {
if(S[i][j]==c[k])map.put(c[k],toint(i,j));
}
}
}
}
BetterGridGraph(int n,int m,char[][] s,char[] c){
N = n;
M = m;
S = s;
map = new HashMap<Character,Integer>();
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
for(int k=0;k<c.length;k++) {
if(S[i][j]==c[k])map.put(c[k],toint(i,j));
}
}
}
}
BetterGridGraph(int n,int m,String[] s,char[] c,char W,char B){
N = n;
M = m;
for(int i=0;i<s.length;i++) {
S[i] = s[i].toCharArray();
}
w = W;
b = B;
map = new HashMap<Character,Integer>();
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
for(int k=0;k<c.length;k++) {
if(S[i][j]==c[k])map.put(c[k],toint(i,j));
}
}
}
}
BetterGridGraph(int n,int m,char[][] s,char[] c,char W,char B){
N = n;
M = m;
S = s;
w = W;
b = B;
map = new HashMap<Character,Integer>();
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
for(int k=0;k<c.length;k++) {
if(S[i][j]==c[k])map.put(c[k],toint(i,j));
}
}
}
}
int toint(int i,int j) {
return i*M+j;
}
int[] bfs(char C) {
int s = map.get(C);
int[] L = new int[N*M];
for(int i=0;i<N*M;i++){
L[i] = -1;
}
L[s] = 0;
ArrayDeque<Integer> Q = new ArrayDeque<Integer>();
Q.add(s);
Range X = new Range(0,N-1);
Range Y = new Range(0,M-1);
while(!Q.isEmpty()){
int v = Q.poll();
for(int i=0;i<4;i++){
int x = v/M;
int y = v%M;
int nx = x+dx[i];
int ny = y+dy[i];
if(X.isIn(nx)&&Y.isIn(ny)&&S[nx][ny]!=b) {
int w = toint(nx,ny);
if(L[w]==-1){
L[w] = L[v] + 1;
Q.add(w);
}
}
}
}
return L;
}
int[][] bfs2(char C,int K){
int s = map.get(C);
int[][] L = new int[N*M][K+1];
for(int i=0;i<N*M;i++){
for(int j=0;j<=K;j++)
L[i][j] = 1000000007;
}
L[s][0] = 0;
ArrayDeque<IntIntPair> Q = new ArrayDeque<IntIntPair>();
Q.add(new IntIntPair(s,0));
Range X = new Range(0,N-1);
Range Y = new Range(0,M-1);
while(!Q.isEmpty()){
IntIntPair v = Q.poll();
for(int i=0;i<4;i++){
int x = v.a/M;
int y = v.a%M;
int h = v.b;
int nx = x+dx[i];
int ny = y+dy[i];
if(X.isIn(nx)&&Y.isIn(ny)&&S[nx][ny]!=b) {
int ni = toint(nx,ny);
int nh = S[nx][ny]==w?h+1:h;
if(nh>K) continue;
if(L[ni][nh]==1000000007){
L[ni][nh] = L[v.a][h] + 1;
Q.add(new IntIntPair(ni,nh));
}
}
}
}
for(int i=0;i<N*M;i++) {
for(int j=1;j<=K;j++) {
L[i][j] = Math.min(L[i][j],L[i][j-1]);
}
}
return L;
}
}
class StringManager{
ArrayList<Character> S;
static Mathplus mp;
static boolean calced;
static int base;
static long baserev;
ArrayList<Long> l;
StringManager(String s){
S = new ArrayList<Character>();
for(int i=0;i<s.length();i++) {
S.add(s.charAt(i));
}
if(!calced) {
calced = true;
mp = new Mathplus();
base = 1000003;
baserev = mp.rev(base);
mp.buildpow(base,1000050);
mp.buildrevpow((int) baserev,1000050);
}
l = new ArrayList<Long>();
l.add((long)S.get(0));
for(int i=1;i<S.size();i++) {
char c = S.get(i);
l.add((l.get(i-1) + mp.pow[i] * c)%mp.mod);
}
}
void add(char C){
int i = S.size();
S.add(C);
l.add((l.get(i-1) + mp.pow[i] * C)%mp.mod);
}
long gethash(int le,int ri) {
long res = l.get(ri);
if(le!=0) {
res -= l.get(le-1);
res += mp.mod;
res %= mp.mod;
res *= mp.revpow[le];
res %= mp.mod;
}
return res;
}
}
class Trie{
int nodenumber = 1;
ArrayList<TrieNode> l;
Trie(){
l = new ArrayList<TrieNode>();
l.add(new TrieNode());
}
void add(String S,int W){
int now = 0;
for(int i=0;i<S.length();i++) {
TrieNode n = l.get(now);
char c = S.charAt(i);
if(n.Exist[c-'a']!=-1) {
now = n.Exist[c-'a'];
}else {
l.add(new TrieNode());
n.Exist[c-'a'] = nodenumber;
now = nodenumber;
nodenumber++;
}
}
l.get(now).weight = W;
}
void find(String S,int i,int[] dp) {
int now = 0;
dp[i+1] = Math.max(dp[i],dp[i+1]);
for(int j=0;;j++) {
TrieNode n = l.get(now);
dp[i+j] = Math.max(dp[i+j],dp[i]+n.weight);
int slook = i+j;
if(slook>=S.length())return;
char c = S.charAt(slook);
if(n.Exist[c-'a']==-1)return;
now = n.Exist[c-'a'];
}
}
}
class TrieNode{
int[] Exist = new int[26];
int weight = 0;
TrieNode(){
for(int i=0;i<26;i++) {
Exist[i] = -1;
}
}
}
class SizeComparator implements Comparator<Edge>{
int[] size;
SizeComparator(int[] s) {
size = s;
}
public int compare(Edge o1, Edge o2) {
return size[o1.to]-size[o2.to];
}
}
class ConvexHullTrick {
long[] A, B;
int len;
public ConvexHullTrick(int n) {
A = new long[n];
B = new long[n];
}
private boolean check(long a, long b) {
return (B[len - 2] - B[len - 1]) * (a - A[len - 1]) >= (B[len - 1] - b) * (A[len - 1] - A[len - 2]);
}
public void add(long a, long b) {
while (len >= 2 && check(a, b)) {
len--;
}
A[len] = a;
B[len] = b;
len++;
}
public long query(long x) {
int l = -1, r = len - 1;
while (r - l > 1) {
int mid = (r + l) / 2;
if (get(mid,x)>=get(mid+1,x)) {
l = mid;
} else {
r = mid;
}
}
return get(r,x);
}
private long get(int k, long x) {
return A[k] * x + B[k];
}
}
class Range{
int l;
int r;
int length;
Range(int L,int R){
l = L;
r = R;
length = R-L+1;
}
boolean isIn(int x) {
return (l<=x&&x<=r);
}
}
class LeftComparator implements Comparator<Range>{
public int compare(Range P, Range Q) {
return P.l-Q.l;
}
}
class RightComparator implements Comparator<Range>{
public int compare(Range P, Range Q) {
return P.r-Q.r;
}
}
class LengthComparator implements Comparator<Range>{
public int compare(Range P, Range Q) {
return P.length-Q.length;
}
}
class SegmentTree<T,E>{
int N;
BiFunction<T,T,T> f;
BiFunction<T,E,T> g;
T d1;
ArrayList<T> dat;
SegmentTree(BiFunction<T,T,T> F,BiFunction<T,E,T> G,T D1,T[] v){
int n = v.length;
f = F;
g = G;
d1 = D1;
init(n);
build(v);
}
void init(int n) {
N = 1;
while(N<n)N*=2;
dat = new ArrayList<T>();
}
void build(T[] v) {
for(int i=0;i<2*N;i++) {
dat.add(d1);
}
for(int i=0;i<v.length;i++) {
dat.set(N+i-1,v[i]);
}
for(int i=N-2;i>=0;i--) {
dat.set(i,f.apply(dat.get(i*2+1),dat.get(i*2+2)));
}
}
void update(int k,E a) {
k += N-1;
dat.set(k,g.apply(dat.get(k),a));
while(k>0){
k = (k-1)/2;
dat.set(k,f.apply(dat.get(k*2+1),dat.get(k*2+2)));
}
}
T query(int a,int b, int k, int l ,int r) {
if(r<=a||b<=l) return d1;
if(a<=l&&r<=b) return dat.get(k);
T vl = query(a,b,k*2+1,l,(l+r)/2);
T vr = query(a,b,k*2+2,(l+r)/2,r);
return f.apply(vl, vr);
}
T query(int a,int b){
return query(a,b,0,0,N);
}
}
class LazySegmentTree<T,E> extends SegmentTree<T,E>{
BiFunction<E,E,E> h;
BiFunction<E,Integer,E> p = (E a,Integer b) ->{return a;};
E d0;
ArrayList<E> laz;
LazySegmentTree(BiFunction<T,T,T> F,BiFunction<T,E,T> G,BiFunction<E,E,E> H,T D1,E D0,T[] v){
super(F,G,D1,v);
int n = v.length;
h = H;
d0 = D0;
Init(n);
}
void build() {
}
void Init(int n){
laz = new ArrayList<E>();
for(int i=0;i<2*N;i++) {
laz.add(d0);
}
}
void eval(int len,int k) {
if(laz.get(k).equals(d0)) return;
if(k*2+1<N*2-1) {
laz.set(k*2+1,h.apply(laz.get(k*2+1),laz.get(k)));
laz.set(k*2+2,h.apply(laz.get(k*2+2),laz.get(k)));
}
dat.set(k,g.apply(dat.get(k), p.apply(laz.get(k), len)));
laz.set(k,d0);
}
T update(int a,int b,E x,int k,int l,int r) {
eval(r-l,k);
if(r<=a||b<=l) {
return dat.get(k);
}
if(a<=l&&r<=b) {
laz.set(k,h.apply(laz.get(k),x));
return g.apply(dat.get(k),p.apply(laz.get(k),r-l));
}
T vl = update(a,b,x,k*2+1,l,(l+r)/2);
T vr = update(a,b,x,k*2+2,(l+r)/2,r);
dat.set(k,f.apply(vl,vr));
return dat.get(k);
}
T update(int a,int b,E x) {
return update(a,b,x,0,0,N);
}
T query(int a,int b,int k,int l,int r) {
eval(r-l,k);
if(r<=a||b<=l) return d1;
if(a<=l&&r<=b) return dat.get(k);
T vl = query(a,b,k*2+1,l,(l+r)/2);
T vr = query(a,b,k*2+2,(l+r)/2,r);
return f.apply(vl, vr);
}
T query(int a,int b){
return query(a,b,0,0,N);
}
}
class AddSumSegmentTree{
int N;
int d1;
ArrayList<Integer> dat;
AddSumSegmentTree(int[] v){
int n = v.length;
init(n);
build(v);
}
void init(int n) {
N = 1;
while(N<n)N*=2;
dat = new ArrayList<Integer>();
}
void build(int[] v) {
for(int i=0;i<2*N;i++) {
dat.add(d1);
}
for(int i=0;i<v.length;i++) {
dat.set(N+i-1,v[i]);
}
for(int i=N-2;i>=0;i--) {
dat.set(i,dat.get(i*2+1)+dat.get(i*2+2));
}
}
void update(int k,int a) {
k += N-1;
dat.set(k,dat.get(k)+a);
while(k>0){
k = (k-1)/2;
dat.set(k,dat.get(k*2+1)+dat.get(k*2+2));
}
}
int query(int a,int b, int k, int l ,int r) {
if(r<=a||b<=l) return d1;
if(a<=l&&r<=b) return dat.get(k);
int vl = query(a,b,k*2+1,l,(l+r)/2);
int vr = query(a,b,k*2+2,(l+r)/2,r);
return vl+vr;
}
int query(int a,int b){
return query(a,b,0,0,N);
}
}
class AddSumLazySegmentTree {
int N;
long[] dat;
long[] laz;
AddSumLazySegmentTree(long[] v){
init(v.length);
for(int i=0;i<v.length;i++) {
dat[N+i-1]=v[i];
}
for(int i=N-2;i>=0;i--) {
dat[i]=dat[i*2+1]+dat[i*2+2];
}
}
void init(int n) {
N = 1;
while(N<n)N*=2;
dat = new long[2*N];
laz = new long[2*N];
}
void eval(int len,int k) {
if(laz[k]==0) return;
if(k*2+1<N*2-1) {
laz[k*2+1] += laz[k];
laz[k*2+2] += laz[k];
}
dat[k] += laz[k] * len;
laz[k] = 0;
}
long update(int a,int b,long x,int k,int l,int r) {
eval(r-l,k);
if(r<=a||b<=l) {
return dat[k];
}
if(a<=l&&r<=b) {
laz[k] += x;
return dat[k]+laz[k]*(r-l);
}
long vl = update(a,b,x,k*2+1,l,(l+r)/2);
long vr = update(a,b,x,k*2+2,(l+r)/2,r);
return dat[k] = vl+vr;
}
long update(int a,int b,long x) {
return update(a,b,x,0,0,N);
}
long query(int a,int b,int k,int l,int r) {
eval(r-l,k);
if(r<=a||b<=l) return 0;
if(a<=l&&r<=b) return dat[k];
long vl = query(a,b,k*2+1,l,(l+r)/2);
long vr = query(a,b,k*2+2,(l+r)/2,r);
return vl+vr;
}
long query(int a,int b){
return query(a,b,0,0,N);
}
}
class BinaryIndexedTree{
int[] val;
BinaryIndexedTree(int N){
val = new int[N+1];
}
long sum(int i) {
if(i==0)return 0;
long s = 0;
while(i>0) {
s += val[i];
i -= i & (-i);
}
return s;
}
void add(int x,int i) {
if(i==0)return;
while(i<val.length){
val[i] += x;
i += i & (-i);
}
}
}
class UnionFindTree {
int[] root;
int[] rank;
int[] size;
int[] edge;
int num;
UnionFindTree(int N){
root = new int[N];
rank = new int[N];
size = new int[N];
edge = new int[N];
num = N;
for(int i=0;i<N;i++){
root[i] = i;
size[i] = 1;
}
}
public boolean isRoot(int x) {
return x==find(x);
}
public int extraEdge(int x) {
int r = find(x);
return edge[r] - size[r] + 1;
}
public int find(int x){
if(root[x]==x){
return x;
}else{
return find(root[x]);
}
}
public void unite(int x,int y){
x = find(x);
y = find(y);
if(x==y){
edge[x]++;
return;
}else{
num--;
if(rank[x]<rank[y]){
root[x] = y;
size[y] += size[x];
edge[y] += edge[x]+1;
}else{
root[y] = x;
size[x] += size[y];
edge[x] += edge[y]+1;
if(rank[x]==rank[y]){
rank[x]++;
}
}
}
}
public boolean same(int x,int y){
return find(x)==find(y);
}
}
class ParticalEternalLastingUnionFindTree extends UnionFindTree{
int[] time;
int now;
ParticalEternalLastingUnionFindTree(int N){
super(N);
time = new int[N];
for(int i=0;i<N;i++) {
time[i] = 1000000007;
}
}
public int find(int t,int i) {
if(time[i]>t) {
return i;
}else {
return find(t,root[i]);
}
}
public void unite(int x,int y,int t) {
now = t;
x = find(t,x);
y = find(t,y);
if(x==y)return;
if(rank[x]<rank[y]){
root[x] = y;
size[y] += size[x];
time[x] = t;
}else{
root[y] = x;
size[x] += size[y];
if(rank[x]==rank[y]){
rank[x]++;
}
time[y] = t;
}
}
public int sametime(int x,int y) {
if(find(now,x)!=find(now,y)) return -1;
int ok = now;
int ng = 0;
while(ok-ng>1) {
int mid = (ok+ng)/2;
if(find(mid,x)==find(mid,y)) {
ok = mid;
}else {
ng = mid;
}
}
return ok;
}
}
class Graph {
ArrayList<Edge>[] list;
int size;
TreeSet<LinkEdge> Edges = new TreeSet<LinkEdge>(new LinkEdgeComparator());
@SuppressWarnings("unchecked")
Graph(int N){
size = N;
list = new ArrayList[N];
for(int i=0;i<N;i++){
list[i] = new ArrayList<Edge>();
}
}
void addEdge(int a,int b){
list[a].add(new Edge(b,1));
}
void addWeightedEdge(int a,int b,long c){
list[a].add(new Edge(b,c));
}
void addEgdes(int[] a,int[] b){
for(int i=0;i<a.length;i++){
list[a[i]].add(new Edge(b[i],1));
}
}
void addWeighterEdges(int[] a ,int[] b ,int[] c){
for(int i=0;i<a.length;i++){
list[a[i]].add(new Edge(b[i],c[i]));
}
}
long[][] bfs(int s){
long[][] L = new long[2][size];
for(int i=0;i<size;i++){
L[0][i] = -1;
L[1][i] = -1;
}
L[0][s] = 0;
ArrayDeque<Integer> Q = new ArrayDeque<Integer>();
Q.add(s);
while(!Q.isEmpty()){
int v = Q.poll();
for(Edge e:list[v]){
int w = e.to;
long c = e.cost;
if(L[0][w]==-1){
L[0][w] = L[0][v] + c;
L[1][w] = v;
Q.add(w);
}
}
}
return L;
}
long[] bfs2(int[] d,int s){
long[] L = new long[size];
for(int i=0;i<size;i++){
L[i] = -1;
}
int p = 0;
L[s] = 0;
d[s] = p;
p++;
ArrayDeque<Integer> Q = new ArrayDeque<Integer>();
Q.add(s);
while(!Q.isEmpty()){
int v = Q.poll();
for(Edge e:list[v]){
int w = e.to;
long c = e.cost;
if(L[w]==-1){
d[w] = p;
p++;
L[w] = L[v] + c;
Q.add(w);
}
}
}
return L;
}
int[] isTwoColor(){
int[] L = new int[size];
for(int i=0;i<size;i++){
L[i] = -1;
}
L[0] = 0;
ArrayDeque<Integer> Q = new ArrayDeque<Integer>();
Q.add(0);
while(!Q.isEmpty()){
int v = Q.poll();
for(Edge e:list[v]){
int w = e.to;
if(L[w]==-1){
L[w] = 1-L[v];
Q.add(w);
}else{
if(L[v]+L[w]!=1){
L[0] = -2;
}
}
}
}
return L;
}
long[] dijkstra(int s){
long[] L = new long[size];
for(int i=0;i<size;i++){
L[i] = -1;
}
int[] v = new int[size];
L[s] = 0;
PriorityQueue<LongIntPair> Q = new PriorityQueue<LongIntPair>(new LongIntSampleComparator());
Q.add(new LongIntPair(0,s));
while(!Q.isEmpty()){
LongIntPair C = Q.poll();
if(v[C.b]==0){
L[C.b] = C.a;
v[C.b] = 1;
for(Edge D:list[C.b]) {
if(L[D.to]==-1||L[D.to]>L[C.b]+D.cost) {
L[D.to]=L[C.b]+D.cost;
Q.add(new LongIntPair(L[C.b]+D.cost,D.to));
}
}
}
}
return L;
}
ArrayList<Graph> makeapart(){
ArrayList<Graph> ans = new ArrayList<Graph>();
boolean[] b = new boolean[size];
int[] num = new int[size];
for(int i=0;i<size;i++){
if(b[i])continue;
int sz = 0;
ArrayList<Integer> l = new ArrayList<Integer>();
ArrayDeque<Integer> Q = new ArrayDeque<Integer>();
Q.add(i);
b[i] = true;
while(!Q.isEmpty()){
int v = Q.poll();
num[v] = sz;
sz++;
l.add(v);
for(Edge e:list[v]){
if(!b[e.to]){
Q.add(e.to);
b[e.to] = true;
}
}
}
Graph H = new Graph(sz);
for(int e:l){
for(Edge E:list[e]){
H.addWeightedEdge(num[e],num[E.to],E.cost);
}
}
ans.add(H);
}
return ans;
}
long[] bellmanFord(int s) {
long inf = 1000000000;
inf *= inf;
long[] d = new long[size];
boolean[] n = new boolean[size];
d[s] = 0;
for(int i=1;i<size;i++){
d[i] = inf;
d[i] *= d[i];
}
for(int i=0;i<size-1;i++){
for(int j=0;j<size;j++){
for(Edge E:list[j]){
if(d[j]!=inf&&d[E.to]>d[j]+E.cost){
d[E.to]=d[j]+E.cost;
}
}
}
}
for(int i=0;i<size;i++){
for(int j=0;j<size;j++){
for(Edge e:list[j]){
if(d[j]==inf) continue;
if(d[e.to]>d[j]+e.cost) {
d[e.to]=d[j]+e.cost;
n[e.to] = true;
}
if(n[j])n[e.to] = true;
}
}
}
for(int i=0;i<size;i++) {
if(n[i])d[i] = inf;
}
return d;
}
long[][] WarshallFloyd(long[][] a){
int n = a.length;
long[][] ans = new long[n][n];
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
ans[i][j] = a[i][j]==0?(long)1e16:a[i][j];
if(i==j)ans[i][j]=0;
}
}
for(int k=0;k<n;k++) {
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
ans[i][j] = Math.min(ans[i][j],ans[i][k]+ans[k][j]);
}
}
}
return ans;
}
long[] maxtra(int s,long l){
long[] L = new long[size];
for(int i=0;i<size;i++){
L[i] = -1;
}
int[] v = new int[size];
L[s] = -1;
PriorityQueue<Pair> Q = new PriorityQueue<Pair>(new SampleComparator());
Q.add(new Pair(l,s));
while(!Q.isEmpty()){
Pair C = Q.poll();
if(v[(int)C.b]==0){
L[(int)C.b] = C.a;
v[(int) C.b] = 1;
for(Edge D:list[(int) C.b])Q.add(new Pair(Math.max(L[(int)C.b],D.cost),D.to));
}
}
return L;
}
long[] mintra(int s){
long[] L = new long[size];
for(int i=0;i<size;i++){
L[i] = -1;
}
int[] v = new int[size];
L[s] = s;
PriorityQueue<Pair> Q = new PriorityQueue<Pair>(new SampleComparator().reversed());
Q.add(new Pair(s,s));
while(!Q.isEmpty()){
Pair C = Q.poll();
if(v[(int)C.b]==0){
L[(int)C.b] = C.a;
v[(int) C.b] = 1;
for(Edge D:list[(int) C.b])Q.add(new Pair(Math.min(L[(int)C.b],D.cost),D.to));
}
}
return L;
}
long Kruskal(){
long r = 0;
for(int i=0;i<size;i++) {
for(Edge e:list[i]) {
Edges.add(new LinkEdge(e.cost,i,e.to));
}
}
UnionFindTree UF = new UnionFindTree(size);
for(LinkEdge e:Edges){
if(e.a>=0&&e.b>=0) {
if(!UF.same(e.a,e.b)){
r += e.L;
UF.unite(e.a,e.b);
}
}
}
return r;
}
ArrayList<Integer> Kahntsort(){
ArrayList<Integer> ans = new ArrayList<Integer>();
PriorityQueue<Integer> q = new PriorityQueue<Integer>();
int[] in = new int[size];
for(int i=0;i<size;i++) {
for(Edge e:list[i])in[e.to]++;
}
for(int i=0;i<size;i++) {
if(in[i]==0)q.add(i);
}
while(!q.isEmpty()) {
int v = q.poll();
ans.add(v);
for(Edge e:list[v]) {
in[e.to]--;
if(in[e.to]==0)q.add(e.to);
}
}
for(int i=0;i<size;i++) {
if(in[i]>0)return new ArrayList<Integer>();
}
return ans;
}
RootedTree dfsTree(int i) {
int[] u = new int[size];
RootedTree r = new RootedTree(size);
dfsTree(i,u,r);
return r;
}
private void dfsTree(int i, int[] u, RootedTree r) {
u[i] = 1;
for(Edge e:list[i]) {
if(u[e.to]==0) {
r.list[i].add(e);
u[e.to] = 1;
dfsTree(e.to,u,r);
}
}
}
}
class Tree extends Graph{
public Tree(int N) {
super(N);
}
long[] tyokkei(){
long[][] a = bfs(0);
System.out.println();
int md = -1;
long m = 0;
for(int i=0;i<size;i++){
if(m<a[0][i]){
m = a[0][i];
md = i;
}
}
long[][] b = bfs(md);
int md2 = -1;
long m2 = 0;
for(int i=0;i<size;i++){
if(m2<b[0][i]){
m2 = b[0][i];
md2 = i;
}
}
long[] r = {m2,md,md2};
return r;
}
}
class RootedTree extends Graph{
RootedTree(int N){
super(N);
}
}
class LinkEdge{
long L;
int a ;
int b;
LinkEdge(long l,int A,int B){
L = l;
a = A;
b = B;
}
public boolean equals(Object o){
LinkEdge O = (LinkEdge) o;
return O.a==this.a&&O.b==this.b&&O.L==this.L;
}
public int hashCode(){
return Objects.hash(L,a,b);
}
}
class Edge{
int to;
long cost;
Edge(int a,long b){
to = a;
cost = b;
}
}
class LinkEdgeComparator implements Comparator<LinkEdge>{
public int compare(LinkEdge P, LinkEdge Q) {
long t = P.L-Q.L;
if(t==0){
if(P.a>Q.a){
return 1;
}else{
return P.b>Q.b?1:-1;
}
}
return t>=0?1:-1;
}
}
class Triplet{
long a;
long b;
long c;
Triplet(long p,long q,long r){
a = p;
b = q;
c = r;
}
public boolean equals(Object o){
Triplet O = (Triplet) o;
return O.a==this.a&&O.b==this.b&&O.c==this.c?true:false;
}
public int hashCode(){
return Objects.hash(a,b,c);
}
}
class TripletComparator implements Comparator<Triplet>{
public int compare(Triplet P, Triplet Q) {
long t = P.a-Q.a;
if(t==0){
long tt = P.b-Q.b;
if(tt==0) {
if(P.c>Q.c) {
return 1;
}else if(P.c<Q.c){
return -1;
}else {
return 0;
}
}
return tt>0?1:-1;
}
return t>=0?1:-1;
}
}
class Pair{
long a;
long b;
Pair(long p,long q){
this.a = p;
this.b = q;
}
public boolean equals(Object o){
Pair O = (Pair) o;
return O.a==this.a&&O.b==this.b;
}
public int hashCode(){
return Objects.hash(a,b);
}
}
class SampleComparator implements Comparator<Pair>{
public int compare(Pair P, Pair Q) {
long t = P.a-Q.a;
if(t==0){
return P.b>=Q.b?1:-1;
}
return t>=0?1:-1;
}
}
class LongIntPair{
long a;
int b;
LongIntPair(long p,int q){
this.a = p;
this.b = q;
}
public boolean equals(Object o){
Pair O = (Pair) o;
return O.a==this.a&&O.b==this.b;
}
public int hashCode(){
return Objects.hash(a,b);
}
}
class LongIntSampleComparator implements Comparator<LongIntPair>{
public int compare(LongIntPair P, LongIntPair Q) {
long t = P.a-Q.a;
if(t==0){
if(P.b>Q.b){
return 1;
}else{
return -1;
}
}
return t>=0?1:-1;
}
}
class IntIntPair{
int a;
int b;
IntIntPair(int p,int q){
this.a = p;
this.b = q;
}
public boolean equals(Object o){
Pair O = (Pair) o;
return O.a==this.a&&O.b==this.b;
}
public int hashCode(){
return Objects.hash(a,b);
}
}
class IntIntSampleComparator implements Comparator<IntIntPair>{
public int compare(IntIntPair P, IntIntPair Q) {
int t = P.a-Q.a;
if(t==0){
return P.b-Q.b;
}
return t;
}
}
class DoublePair{
double a;
double b;
DoublePair(double p,double q){
this.a = p;
this.b = q;
}
public boolean equals(Object o){
Pair O = (Pair) o;
return O.a==this.a&&O.b==this.b;
}
public int hashCode(){
return Objects.hash(a,b);
}
}
class DDSampleComparator implements Comparator<DoublePair>{
public int compare(DoublePair P, DoublePair Q) {
return P.b-Q.b>=0?1:-1;
}
}
class DoubleTriplet{
double a;
double b;
double c;
DoubleTriplet(double p,double q,double r){
this.a = p;
this.b = q;
this.c = r;
}
public boolean equals(Object o){
DoubleTriplet O = (DoubleTriplet) o;
return O.a==this.a&&O.b==this.b&&O.c==this.c;
}
public int hashCode(){
return Objects.hash(a,b,c);
}
}
class FastScanner {
private final java.io.InputStream in = System.in;
private final byte[] b = new byte[1024];
private int p = 0;
private int bl = 0;
private boolean hNB() {
if (p<bl) {
return true;
}else{
p = 0;
try {
bl = in.read(b);
} catch (IOException e) {
e.printStackTrace();
}
if (bl<=0) {
return false;
}
}
return true;
}
private int rB() { if (hNB()) return b[p++]; else return -1;}
private static boolean iPC(int c) { return 33 <= c && c <= 126;}
private void sU() { while(hNB() && !iPC(b[p])) p++;}
public boolean hN() { sU(); return hNB();}
public String next() {
if (!hN()) throw new NoSuchElementException();
StringBuilder sb = new StringBuilder();
int b = rB();
while(iPC(b)) {
sb.appendCodePoint(b);
b = rB();
}
return sb.toString();
}
public char nextChar() {
return next().charAt(0);
}
public long nextLong() {
if (!hN()) throw new NoSuchElementException();
long n = 0;
boolean m = false;
int b = rB();
if (b=='-') {
m=true;
b=rB();
}
if (b<'0'||'9'<b) {
throw new NumberFormatException();
}
while(true){
if ('0'<=b&&b<='9') {
n *= 10;
n += b - '0';
}else if(b == -1||!iPC(b)){
return (m?-n:n);
}else{
throw new NumberFormatException();
}
b = rB();
}
}
public int nextInt() {
if (!hN()) throw new NoSuchElementException();
long n = 0;
boolean m = false;
int b = rB();
if (b == '-') {
m = true;
b = rB();
}
if (b<'0'||'9'<b) {
throw new NumberFormatException();
}
while(true){
if ('0'<=b&&b<='9') {
n *= 10;
n += b-'0';
}else if(b==-1||!iPC(b)){
return (int) (m?-n:n);
}else{
throw new NumberFormatException();
}
b = rB();
}
}
public int[] nextInts(int n) {
int[] a = new int[n];
for(int i=0;i<n;i++) {
a[i] = nextInt();
}
return a;
}
public long[] nextLongs(int n) {
long[] a = new long[n];
for(int i=0;i<n;i++) {
a[i] = nextLong();
}
return a;
}
public int[][] nextIntses(int n,int m){
int[][] a = new int[n][m];
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
a[i][j] = nextInt();
}
}
return a;
}
}
class Mathplus{
int mod = 1000000007;
long[] fac;
long[] revfac;
long[][] comb;
long[] pow;
long[] revpow;
boolean isBuild = false;
boolean isBuildc = false;
boolean isBuildp = false;
int mindex = -1;
int maxdex = -1;
int color(int[][] diff,int N) {
int[] val = new int[1<<N];
val[0] = 1;
for(int i=0;i<(1<<N);i++) {
for(int j=0;j<N;j++) {
if(contains(i,j)) {
if(val[bitremove(i,j)]==1) {
boolean b = true;
for(int k=0;k<N;k++) {
if(contains(i,k)&&diff[j][k]==1) {
b = false;
}
}
if(b)val[i] = 1;
}
break;
}
}
}
int[] dp = new int[1<<N];
Arrays.fill(dp,mod);;
dp[0] = 0;
for(int i=0;i<(1<<N);i++) {
for(int j=i;j>0;j=(j-1)&i) {
if(val[j]==1)dp[i]=Math.min(dp[i],dp[i^j]+1);
}
}
return dp[(1<<N)-1];
}
public DoubleTriplet Line(double x1,double y1,double x2,double y2) {
double a = y1-y2;
double b = x2-x1;
double c = x1*y2-x2*y1;
return new DoubleTriplet(a,b,c);
}
public double putx(DoubleTriplet T,double x) {
return -(T.a*x+T.c)/T.b;
}
public double puty(DoubleTriplet T,double y) {
return -(T.b*y+T.c)/T.a;
}
public double DistanceofPointandLine(DoublePair P,Triplet T) {
return Math.abs(P.a*T.a+P.b*T.b+T.c) / Math.sqrt(T.a*T.a+T.b*T.b);
}
public boolean cross(long ax, long ay, long bx, long by, long cx, long cy, long dx, long dy) {
long ta = (cx - dx) * (ay - cy) + (cy - dy) * (cx - ax);
long tb = (cx - dx) * (by - cy) + (cy - dy) * (cx - bx);
long tc = (ax - bx) * (cy - ay) + (ay - by) * (ax - cx);
long td = (ax - bx) * (dy - ay) + (ay - by) * (ax - dx);
return((tc>=0&&td<=0)||(tc<=0&&td>=0))&&((ta>=0&&tb<=0)||(ta<=0&&tb>=0));
}
public boolean dcross(double ax, double ay, double bx, double by, double cx, double cy, double dx, double dy) {
double ta = (cx - dx) * (ay - cy) + (cy - dy) * (cx - ax);
double tb = (cx - dx) * (by - cy) + (cy - dy) * (cx - bx);
double tc = (ax - bx) * (cy - ay) + (ay - by) * (ax - cx);
double td = (ax - bx) * (dy - ay) + (ay - by) * (ax - dx);
return((tc>=0&&td<=0)||(tc<=0&&td>=0))&&((ta>=0&&tb<=0)||(ta<=0&&tb>=0));
}
void buildFac(){
fac = new long[10000003];
revfac = new long[10000003];
fac[0] = 1;
for(int i=1;i<=10000002;i++){
fac[i] = (fac[i-1] * i)%mod;
}
revfac[10000002] = rev(fac[10000002])%mod;
for(int i=10000001;i>=0;i--) {
revfac[i] = (revfac[i+1] * (i+1))%mod;
}
isBuild = true;
}
void buildFacn(int n){
fac = new long[n+1];
revfac = new long[n+1];
fac[0] = 1;
for(int i=1;i<=n;i++){
fac[i] = (fac[i-1] * i)%mod;
}
revfac[n] = rev(fac[n])%mod;
for(int i=n-1;i>=0;i--) {
revfac[i] = (revfac[i+1] * (i+1))%mod;
}
isBuild = true;
}
public long[] buildrui(int[] a) {
int n = a.length;
long[] ans = new long[n];
ans[0] = a[0];
for(int i=1;i<n;i++) {
ans[i] = ans[i-1] + a[i];
}
return ans;
}
public int[][] ibuildrui(int[][] a) {
int n = a.length;
int m = a[0].length;
int[][] ans = new int[n][m];
for(int i=1;i<n;i++) {
for(int j=1;j<m;j++) {
ans[i][j] = a[i][j];
}
}
for(int i=1;i<n;i++) {
for(int j=1;j<m;j++) {
ans[i][j] += ans[i][j-1] + ans[i-1][j] - ans[i-1][j-1];
}
}
return ans;
}
public void buildruin(int[][] a) {
int n = a.length;
int m = a[0].length;
for(int i=1;i<n;i++) {
for(int j=1;j<m;j++) {
a[i][j] += a[i][j-1] + a[i-1][j] - a[i-1][j-1];
}
}
}
public long[][] buildrui(int[][] a) {
int n = a.length;
int m = a[0].length;
long[][] ans = new long[n][m];
for(int i=1;i<n;i++) {
for(int j=1;j<m;j++) {
ans[i][j] = a[i][j];
}
}
for(int i=1;i<n;i++) {
for(int j=1;j<m;j++) {
ans[i][j] += ans[i][j-1] + ans[i-1][j] - ans[i-1][j-1];
}
}
return ans;
}
long divroundup(long n,long d) {
if(n==0)return 0;
return (n-1)/d+1;
}
public long sigma(long i) {
return i*(i+1)/2;
}
public int digit(long i) {
int ans = 1;
while(i>=10) {
i /= 10;
ans++;
}
return ans;
}
public int popcount(int i) {
int ans = 0;
while(i>0) {
ans += i%2;
i /= 2;
}
return ans;
}
public boolean contains(int S,int i) {return (S>>i&1)==1;}
public int bitremove(int S,int i) {return S&(~(1<<i));}
public int bitadd(int S,int i) {return S|(1<<i);}
public boolean isSubSet(int S,int T) {return (S-T)==(S^T);}
public boolean isDisjoint(int S,int T) {return (S+T)==(S^T);}
public int isBigger(int[] d, int i) {
int ok = d.length;
int ng = -1;
while(Math.abs(ok-ng)>1) {
int mid = (ok+ng)/2;
if(d[mid]>i) {
ok = mid;
}else {
ng = mid;
}
}
return ok;
}
public int isSmaller(int[] d, int i) {
int ok = -1;
int ng = d.length;
while(Math.abs(ok-ng)>1) {
int mid = (ok+ng)/2;
if(d[mid]<i) {
ok = mid;
}else {
ng = mid;
}
}
return ok;
}
public int isBigger(long[] d, long i) {
int ok = d.length;
int ng = -1;
while(Math.abs(ok-ng)>1) {
int mid = (ok+ng)/2;
if(d[mid]>i) {
ok = mid;
}else {
ng = mid;
}
}
return ok;
}
public int isSmaller(long[] d, long i) {
int ok = -1;
int ng = d.length;
while(Math.abs(ok-ng)>1) {
int mid = (ok+ng)/2;
if(d[mid]<i) {
ok = mid;
}else {
ng = mid;
}
}
return ok;
}
public int isBigger(ArrayList<Long> d, long i) {
int ok = d.size();
int ng = -1;
while(Math.abs(ok-ng)>1) {
int mid = (ok+ng)/2;
if(d.get(mid)>i) {
ok = mid;
}else {
ng = mid;
}
}
return ok;
}
public int isSmaller(ArrayList<Long> d, long i) {
int ok = -1;
int ng = d.size();
while(Math.abs(ok-ng)>1) {
int mid = (ok+ng)/2;
if(d.get(mid)<i) {
ok = mid;
}else {
ng = mid;
}
}
return ok;
}
public HashSet<Integer> primetable(int m) {
HashSet<Integer> pt = new HashSet<Integer>();
for(int i=2;i<=m;i++) {
boolean b = true;
for(int d:pt) {
if(i%d==0) {
b = false;
break;
}
}
if(b) {
pt.add(i);
}
}
return pt;
}
public ArrayList<Integer> primetablearray(int m) {
ArrayList<Integer> al = new ArrayList<Integer>();
Queue<Integer> q = new ArrayDeque<Integer>();
for(int i=2;i<=m;i++) {
q.add(i);
}
boolean[] b = new boolean[m+1];
while(!q.isEmpty()) {
int e = q.poll();
if(!b[e]) {
al.add(e);
for(int j=1;e*j<=1000000;j++) {
b[e*j] = true;
}
}
}
return al;
}
public HashMap<Integer,Integer> hipPush(ArrayList<Integer> l){
HashMap<Integer,Integer> r = new HashMap<Integer,Integer>();
TreeSet<Integer> s = new TreeSet<Integer>();
for(int e:l)s.add(e);
int p = 0;
for(int e:s) {
r.put(e,p);
p++;
}
return r;
}
public TreeMap<Integer,Integer> thipPush(ArrayList<Integer> l){
TreeMap<Integer,Integer> r = new TreeMap<Integer,Integer>();
Collections.sort(l);
int b = -(mod+9393);
int p = 0;
for(int e:l) {
if(b!=e) {
r.put(e,p);
p++;
}
b=e;
}
return r;
}
long max(long[] a){
long M = 0;
for(int i=0;i<a.length;i++){
if(M<a[i]){
M =a[i];
maxdex = i;
}
}
return M;
}
int max(int[] a){
int M = 0;
for(int i=0;i<a.length;i++){
if(M<a[i]){
M =a[i];
maxdex = i;
}
}
return M;
}
long min(long[] a){
long m = Long.MAX_VALUE;
for(int i=0;i<a.length;i++){
if(m>a[i]){
m =a[i];
mindex = i;
}
}
return m;
}
int min(int[] a){
int m = Integer.MAX_VALUE;
for(int i=0;i<a.length;i++){
if(m>a[i]){
m =a[i];
mindex = i;
}
}
return m;
}
long sum(long[] a){
long s = 0;
for(int i=0;i<a.length;i++)s += a[i];
return s;
}
long sum(int[] a){
long s = 0;
for(int i=0;i<a.length;i++)s += a[i];
return s;
}
long gcd(long a, long b){
a = Math.abs(a);
b = Math.abs(b);
if(a==0)return b;
if(b==0)return a;
if(a%b==0) return b;
else return gcd(b,a%b);
}
int igcd(int a, int b) {
if(a%b==0) return b;
else return igcd(b,a%b);
}
long lcm(long a, long b) {return a / gcd(a,b) * b;}
public long perm(int a,int num) {
if(!isBuild)buildFac();
return fac[a]*(rev(fac[a-num]))%mod;
}
void buildComb(int N) {
comb = new long[N+1][N+1];
comb[0][0] = 1;
for(int i=1;i<=N;i++) {
comb[i][0] = 1;
for(int j=1;j<N;j++) {
comb[i][j] = comb[i-1][j-1]+comb[i-1][j];
if(comb[i][j]>mod)comb[i][j]-=mod;
}
comb[i][i] = 1;
}
}
public long comb(int a,int num){
if(a-num<0)return 0;
if(num<0)return 0;
if(!isBuild)buildFac();
return fac[a] * ((revfac[num]*revfac[a-num])%mod)%mod;
}
long mulchoose(int n,int k) {
if(k==0) return 1;
return comb(n+k-1,k);
}
long rev(long l) {return pow(l,mod-2);}
void buildpow(int l,int i) {
pow = new long[i+1];
pow[0] = 1;
for(int j=1;j<=i;j++) {
pow[j] = pow[j-1]*l;
if(pow[j]>mod)pow[j] %= mod;
}
}
void buildrevpow(int l,int i) {
revpow = new long[i+1];
revpow[0] = 1;
for(int j=1;j<=i;j++) {
revpow[j] = revpow[j-1]*l;
if(revpow[j]>mod) revpow[j] %= mod;
}
}
long pow(long l, long i) {
if(i==0)return 1;
else{
if(i%2==0){
long val = pow(l,i/2);
return val * val % mod;
}
else return pow(l,i-1) * l % mod;
}
}
long mon(int i) {
long ans = 0;
for(int k=2;k<=i;k++) {
ans += (k%2==0?1:-1) * revfac[k];
ans += mod;
}
ans %= mod;
ans *= fac[i];
return ans%mod;
}
}