public class DerangementHelper extends java.lang.Object
{
	private DerangementHelper()
	{
		super();
	}

	public static <T> T[] derange(T[] input)
	{
		T[] rv=(T[])new java.lang.Object[input.length];
		java.util.Map<java.lang.Integer,T> map=new java.util.HashMap();
		for(int i=0;i<input.length;++i)
			map.put(java.lang.Integer.valueOf(i),input[i]);
		java.util.Map<java.lang.Integer,T> l=derange(map);
		for(java.util.Map.Entry<java.lang.Integer,T> entry:l.entrySet())
		{
			rv[entry.getKey().intValue()]=entry.getValue();
		}
		return rv;
	}
	public static <T> java.util.List<T> derange(java.util.List<T> input)
	{
		T[] rv=(T[])new java.lang.Object[input.size()];
		java.util.Map<java.lang.Integer,T> map=new java.util.HashMap();
		for(int i=0;i<input.size();++i)
			map.put(java.lang.Integer.valueOf(i),input.get(i));
		java.util.Map<java.lang.Integer,T> l=derange(map);
		for(java.util.Map.Entry<java.lang.Integer,T> entry:l.entrySet())
		{
			rv[entry.getKey().intValue()]=entry.getValue();
		}
		return java.util.Arrays.asList(rv);
	}
	public static <T,U> java.util.Map<T,U> derange(java.util.Map<T,U> input)
	{
		java.util.Map<T,U> rv=new java.util.HashMap();
		java.util.List<java.util.Map.Entry<T,U> > l=new java.util.LinkedList();
		for(java.util.Map.Entry<T,U> entry:input.entrySet())
		{
			if(entry.getKey()==null)
				throw new java.lang.NullPointerException();
			else
				l.add(entry);
		}
		java.util.Collections.shuffle(l);
		T latch=null;
		for(java.util.Map.Entry<T,U> entry:l)
		{
			if(latch==null)
				latch=l.get(l.size()-1).getKey();
			rv.put(latch,entry.getValue());
			latch=entry.getKey();
		}
		return rv;
	}
	/*public static void main(java.lang.String[] ergs)
	{
		java.util.Map<java.lang.Integer,java.lang.Integer> map=new java.util.HashMap();
		for(int i=0;i<30;++i)
		{
			map.put(java.lang.Integer.valueOf(i),java.lang.Integer.valueOf(i));
		}
		map=DerangementHelper.derange(map);
		for(Map.Entry entry:map.entrySet())
		{
			if(entry.getKey().equals(entry.getValue()))
				System.exit(1);
			else
				System.out.println(entry.getKey()+" "+entry.getValue());
		}
		System.out.println("ok!");
		java.util.List<java.lang.Integer> list=new java.util.LinkedList();
		for(int i=0;i<30;++i)
		{
			list.add(java.lang.Integer.valueOf(i));
		}
		list=DerangementHelper.derange(list);
		for(int i=0;i<list.size();++i)
		{
			if(list.get(i).equals(java.lang.Integer.valueOf(i)))
				System.exit(1);
			else
				System.out.println(list.get(i)+" "+i);
		}
		System.out.println("ok!");
	}*/
}